After a little moan about it on Twitter, my friend Adrian pointed me in the right direction. Even though during the installation the installer confirms the location of the JDK, it still can't find it.
So you just need to:
- Find where you installed Android Studio
- Open Studio.bat
- Add this line -> set JDK_HOME=C:\Program Files\Java\jdk1.7.0_03 (two lines below @ECHO OFF)
- Run Android Studio.