When I take of to cruise alt between FL300 and FL350 my FPS is around 80-100 (depending on the aircraft) When I fly the 707 i have lower FPS then when on 727. Did you try another aircraft for your flights see if that improves the FPS?
I've tried everything from freeware GA to the CS 767-300.

Also, what programs do you have running in the background? Are you playing with IE or FF during flights?
Before I start FSX, I close all programs, close unnecessary notification items, and run disk cleaner to delete around 200MB of hard disk space (not much, but why not?).

Also, look in your config panel and your Power Options. Make sure it is on high performance.
It is.

Also, make sure all your drivers are up to date. You can download a very handy tool on the AMD site to automatize checking if you have up to date video drivers and will update when they are not updated.
I do this a lot--it helps.

Also run the automatic updates for Windows.
Don't do this much, I'll try running that.

Last but not least, do you run FSX with SP2?  
I have Acceleration.

It seems that the issue is my graphics card, so I'll probably order a new if not today, soon. Would you recommend the NVIDIA GeForce GTX 560 TI?

Also, the NVIDIA 560 TI and the AMD 6870 require 500 watts of power. It looks like my computer (and I would think this is the same for yours) only supplies 460 watts. Do I need to buy a new power supply?  :-/

Oh, and sorry for all the questions, but I haven't done much hardware upgrading except RAM. Why are there so many different types and prices for the same video card (besides the variation in memory--512md or 1gb)? Are some better than others?