To be honest, I haven't used a JVM under Windows in a long time because I use Linux for everything besides games.
It sounds like you downloaded and attempted to install the right software; I assume you've repeated the installation process just in case.
Only other ideas are to go with a different SDK version (i.e. 1.3.1) or the MS VM if you're really desperate. Or you could investigate IE's mechanism for installing plugins; maybe you can diagnose why the SDK is installed but the browser plugin doesn't seem registered.
Are you a programmer or just an end user who needs Java applet support? If the latter, the Java2 RE is all you need (it's the same VM as the SDK, without development tools). Not that the RE would work when the SDK doesn't, but just checking what you want a JVM for.
Sorry I can't be more specific.