In my case, the problem was that a line feed had gotten into the setting of the JAVA_HOME variable. I'm not sure how, but I was mucking with it earlier because I had had an issue with an unrelated ant build that was using JAVA_HOME, and I copied the path in.
I noticed the problem partially when I did a "set" command from the command line, and it showed "JAVA_HOME" on one line and the path on the next line, and a blank line after it.
But what really helped was running the gradle command. It gave the same error message. That gave me confidence that the problem really was the JAVA_HOME variable, and not the Android Studio install.
To solve the problem, I deleted the JAVA_HOME variable first. Then, when setting up the command to set the variable, I keyed in the path manually in Textpad, to make sure there were no linefeeds or carriage returns.
Then I ran the command:
setx JAVA_HOME "C:\Program Files\Java\jdk1.7.0_71"