For both my wife and myself, on both of our 4G phones (android, HTC EVO 4G and EVO 3D) the app starts quickly but once we select a car, it takes minutes for the next screen to come up.
I pretty easily get 5Mb down and 2Mb up with my connection in the city, so that's not the issue. But when I select my car from the list on the main screen, if I do this when I start pumping gas it usually only loads around the time the tank is done filling. And for my wife, it still usually hasn't loaded.
Once I enter the data and hit Fill Up, then the next page loads fairly quickly.
Another option is to try clicking the 'Basic' link at the bottom of any Mobile Fuelly page. That will remove all styling and effects. There could be a page transition that's eating up processing or something. The basic version won't look as fancy, but it should at least eliminate the possibility that page effects are causing problems.
Oh, one more thing. Just to check—are you starting Fuelly in a browser, or with the unofficial launcher in the Android app store? If you're using the app, you might just try loading Fuelly Mobile in your browser and see if that's causing the problem