As a fellow sufferer of low FPS I have found it to be Graphics Card related too. I agree with the previous poster about disabling VBO with ATI graphics cards, though I hafta say when I had eventually tried everything else and switched my Graphics card to NVidia it made a huge difference. I then bought a new puter with way more power and sadly another ATI card and the problem came back lol
Out of interest, if you cam up so that there is nothing on your screen except for clear sky (by nothing I mean not even clouds, you can switch those off in Advanced >> Rendering on one of the sub-menus) does your FPS then shoot up to 30-50 fps? If so, you can safely say it is definately related to the Graphics card.
Also what speed is your connection?