Several Problem...All Related?

Computer has recently become:

• increasingly slow
• blue screen warning message "Warning! Spyware detected on your computer! Install an antivirus or spyware remover to clean your computer" this cannot be removed from desktop
• explorer bar cannot be accessed only one quarter of it showing (the top of it), you cant access start, etc
• icons on desktop are locked in place cannot be moved, although in arrange icons menu it appears they are not
• Bullguard (the active virus/firewall i am currently using) doesnt seem to be working: "failed to communicate with email service", "could not communicate with the firewall service.."
• before welcome screen where you log onto various users the "Warning! Spyware detected screen" is also displayed

Is it at all possible to fix these problems or are such attempts futile and i should simply reinstall XP????

Any help would be greatly appreciated. thanks in advance.