Perhaps a silly question, but is it a bitness issue? I'm not familiar with Minecraft, but some Java programs get fussy about that.
If you've just installed the 64 bit JRE then try grabbing the 32 bit one also (or vice versa) -it may then be able to find it.