I think that you have 2 problems that may or may not be related.

PC reboots - sounds more like a bad driver or file. The PC automatically rebooting is the XP'ish BSOD. To see whats really going on, turn off the reboot. Right click the My computer icon, left click properties, click the Advanced tab, and then click the Settings button in the Startup and Recovery section. In the next Window that pops up, uncheck the 'Automatically restart' option and ok out of everything. Now try your video chat program and write down the error that occurs. Also, try the NAV and write down that error as well.

The 'mysterious programs' and the browser hijack probably just needs to be cleaned. If spybot didnt show anything, than I would try Adaware (there's a free version somewhere on that page). Once those are run (and run them a few times), then reset your browser homepage back to what you want.