Você instalou o Java 32bit ou o Java 64bit? Isso é importante, pois a maioria dos navegadores é um software de 32 bits, portanto, eles precisam do Java de 32 bits instalado para que possam usá-lo.
Como o OP declarou, há duas maneiras de contornar isso:
Use um navegador de 64 bits (se disponível) e use Java de 64 bits
ou
Como os navegadores normalmente ainda são de 32 bits, instale o Java de 32 bits (você pode ter o Java de 32 e 64 bits)