Laptop got infected, now can't access the Internet

Yes system restore will put your pc back to the date of the restore point. And it will perform as it did then. BUT you can already see the problem, Everything you did after that point will be gone. You would do well to save all the work you value off the pc, to a external HDD or DVD's or Flash stick. It's a good idea to force a restore point every couple of weeks, for this very reason.
If you use a web based email account then that's safe.
If you use Outlook etc, try;
http://www.retinaxstudios.com/ezemailbackup/overview.php
(this seems to be free, there are others easily found on 'net)
You were right to suspect a program that finds viruses and then offers to fix them for you, seen the same here. All looks genuine, that's the problem !
If you have an effective antivirus program, you would do well to go into 'safe mode' and do a full scan, could take time, but worth it.
It could be all you need to do is set up your wireless connection again, if you have a setup cd as part of your wireless modem/router, or use windows setup routine.
But of course use the Restore as the last option.

I did not see anything on this particular issue: Internet Security Solutions. but you were right in thinking it dodgy. Whenever something pops up and promises to fix your computer, beware.
You said you think you have removed it. Before you proceed with restoring anything, backup your data and make sure you have removed it.
Malwarebytes is currently considered the best for ridding yourself of this kind of scum. www.malwarebytes.org
Have you run SFC /scannow to repair any damaged or missing windows files?
Some malware programs rename *.exe files so you can no longer run them.
If all else fails I rely on Langa's no re-format Nondestructive Total-Rebuild Option
for XP, is this XP?

http://www.informationweek.com/news/windows/showArticle.jhtml?articleID=189400897

No it's Vista. I'm at work at the moment but I will try Malwarebytes when I get home. If that, nor setting up the wireless connection again works, I guess I'll have to go for the restore ;/ I read in Windows Help that System Restore doesn't affect your personal files though?

Whenever a virus infects my PC in a way that it doesnt work right after a scan, i usually find it best to just reinstall Windows.

If you decide to do that, back up your data first.

Here's an option (once the virus is removed) to restore your network connections:

http://www.rizone3.com/archives/1308

Run that and check all the options. It will repair your network configuration.

nissanman said:

Whenever a virus infects my PC in a way that it doesnt work right after a scan, i usually find it best to just reinstall Windows.

If you decide to do that, back up your data first.

Click to expand...

I did the exact same thing about a week ago and it somehow managed to save the system

Always good to save the system first. Most companies just blow it out and restore the image of the laptop into a new build then restore prior saved profiles. Home users can do the same thing too if you have the time to first backup the system image. So if a pest lurks into your system you can do image restore.

Malwarebytes sorted the problem so thanks for all the help guys, much appreciated.