I had previously noted that I installed Qt Creator 3.0 and it automatically detected compiler toolchains, CMake etc. At that time I was running VS 2010 Professional. I recently moved to VS 2013 Express. I opened up a new CMake project in Qt Creator and noticed that suddenly it no longer gave me the option for the proper NMake generator and started failing. After much mucking about, I have finally discovered the solution and just documenting it here in case someone else comes across the same issue.
The solution is simple. Simply install the newly released Qt Creator 3.1. Qt Creator 3.1 has inbuilt support for detecting and using VS 2013 compilers with CMake. Qt Creator 3.0 detects the compilers succesfully but was not really passing the right arguments to CMake or something. Anyway, after updating to 3.1, all my CMake projects work now.