I would definitely run Spybot before looking anywhere else. If the toolbar was the Google toolbar, that could have been blocking sites, but also would not be seen by Spybot (as it is a totally optional install, with few(?) strings attached).

I am the Doctor, and THIS... is my SPOON!