It's not too incredibly hard, I always try a few simple things before going through re-formating. Yes it's easier than pre xp OS's, but still time consuming to re-load all programs.

Run -> Regedit

HKeyLocalMachine -> Software -> Microsoft -> Windows -> Current Version -> Run

Also do the same under HKeyLocalUser

Delete all unnecessary startup paths. I.E. Everything but your virus protection. Also a quick Lavasoft Adaware scan will help. Available at download.com.

Hope this helps!