I was having the same problem earlier today. My homepage had also become the same as you mentioned above.
All sorts of icons appeared all over my desktop and down by the clock was a warning saying i had become infected with a virus. all icons and the virus warning sent me to a page advertising Spywarequake software.
I've been deleting it all all day, ripping stuff out of my registry and deleting everthing on my computer that had anythign to do with it. I removed the Spyware quake program 16 times and it kept re installing from somewhere.
I went to the site and had a good poke about and found a page that allowed me to messege them incase i had lost my licence key, in the event that i paid them for their software LOL!
I sent a polite messege instead telling them of how it was insulting and hypocritical to fill someones computer with spyware that harrassed people into buying antispyware software. I also informed them that i was not going to give them a penny and would use any software but theirs to remove their spyware.
Miraculously 30 mins later, the pop up and the flashing icon next to my clock all just dissapeared and stopped. It's all gone now.
I'm running ADware and have trends free trial scanning my PC and removing some of the remaining bits and bobs but basically the attacks have ceased which is what matters.
[Edit]
The attacks started again. I went through the recommended processes and removed all the files and registry entries any of the scanners could find, (that had anything to do with the problem) The final file that was making the icon come up near my windows clock was only detected by bitdefender's online scan. (Which i was very impressed with)
The file was named stickrep.dll
This file was undeletable even in safemode and bitdefender couldn't remove it either.
My final solution which seems to have done the trick was move the file directly to the C:\ so it was readily accessable and i booted up in Safemode with command prompt. From there i typed in,
CD C:\
which took me to the C drive and i ran Explorer.exe
I have the explorer file shortcuted on my quickbar which allowed me fast access to read through the files on my C drive and quickly delete Stickrep.exe
I could then empty the recycle bin.
My computer has been completely back to normal since.
Many thanks, the information i have found on this site has been a holy grail to someone in my situation. I wouldn't have been able to do this without this site.