Mid 2009 MBP has internet connection on some programs, but not all

[ghulst]

Over the past couple of weeks, my 13" MBP seems to have developed an annoying problem. It shows it is connected to my WIFI router, but even though Dropbox, Skype etc still show a connection (and work), my browsers and Spotify often report to be offline. Switching off Wifi and reconnecting often results in those programs that were still working to lose their connection as well. Rebooting often resolves the problem for a while, but then after a while it will resurface.
When the wifi connection is lost and I plug in an ethernet cable, the connection does not come back. When I plug in a PC, the connection is up and great. On wifi as well.

This is really annoying. Anyone got any suggestions?

Help!

 

[NinjaDuck]

Try doing a clean install of OS X.

 

[ghulst]

Try doing a clean install of OS X.

I was afraid someone was going to come out and say that...

Any tips on the best way to do it? I have bad experiences in building USB installers. Most of them do not tend to work for me for completely clean installs.
And should I recover from TimeMachine, or do it another way?

(Yes, I have been a mac user for 4 years now and I have never had to do a clean install. - Oh, and I would rather wait for Mavericks to do it all at once.)