If you didn't have Windows up to date before you installed SP2, that updat may have uninstalled the Microsoft Java Virtual Machine (MSJVM). Lot of legal wrangling between MS and Sun and don't know where they stand now, but at one point the MSJVM was uninstalled by the SP1a update, I believe.
In any event, a fresh install of the Sun JVM is much more secure and usually easy to do. It will plug into IE when installed--at least I don't remember having to do anything special. And with Firefox you would be asked if you want to install the plug-in when you try to open a Java applet so it's pretty painless. I would try a reinstall of Java as already mentioned.
You can check on the status of the plugins before hand to satisfy your curiosity--and mine.
Go to C:\WINDOWS\Downloaded Program Files and look for files named Java Runtime Environment. Right click and choose Properties. If the Status says damaged or anything other than Installed then there is your problem. You can right click on these JRE files and then click Remove to uninstall them, but it would be better to Uninstall them thru Add/Remove Programs first if they show up there. Then go back to the DPF folder and remove any JRE files that might be there.
You can download Sun Java here:http://www.java.com/en/download/windows_automatic.jsp
You may have to try the manual download--and if any problems their Help and FAQ links are pretty good.
Let us know how it goes.
And BTW, Java doesn't have anything to do with Flash--that's a whole different plug-in.