A few more questions.
When you got a new router, was it the same brand/model?
If so, did you double check that you have the most up to date firmware?
Was it a linksys router? (I have the most problems with linksys/cisco)
In Kismet, looking at the traffic map, especially for those networks within 4 channels from your channel will give you a good idea of if there is interference.
Another tool that might help and be easier to use:
http://www.istumbler.net/
Look at the noise ratios. Higher noise means more collisions and more likelihood of failed connections.
If it looks like the signals are clear, I would try creating a new user account on the machine and try with the new account to see if that helps.
If it looks like the channels are clogged, I would do something that isn't "allowed." I would install DD-WRT or other similar alternative OS on my router (assuming yours is a supported model). Using this, I would set my router to channel 13. Its almost guaranteed to be in the clear as its not allowed to be used in the US by default. It is totally legal to use under 50db though, so no worries there.
Outside of that... the reformat is an idea. But I would certainly test a linux live cd first.