Do you have a shortcut on the desktop for 'Windows Explorer'. If so access System Tools and then System Restore. Roll back the Laptop to a date before you got the virus. Hopefully this should restore Start Button function.
Can't guarunte this will work but it's seems to be a logical step.
Failing that if you have the manufacturers recovery disk try that using the 'Nondestructive System Recovery' option. That should reset all System files to default.