It could be your graphics. a review of that GPU here:
http://www.notebookcheck.net/AMD-ATI...0.13883.0.html
Scroll down to WoW ,shows 2005 BC version if thats what they tested, has it at mid detail. As most long term wow players know, Lich King changed the performance. what was once High detail machines have dropped to Med or Low.
Now that in mind, combined with poor bandwidth?
Also, brand new your system was in its cleanest and top form, I'm sure you have installed or removed a few things since?
Anything update between the time of the change? Newest version doesn't mean best. Seen it a few times with video drivers, update and things get worse.