I have this problem on my Windows 8 laptop. I tracked the problem to the new shutdown process with Windows 8. It won't do a full shutdown/startup when you do, only some sort of hybrid shutdown (https://superuser.com/questions/496241/are-there-downsides-to-windows-8-hybrid-shutdown)
I found that if I use the normal Charm -> Settings -> Power -> Shutdown, it would fail to load the encrypted partition when I got to the desktop.
However, if you use the command line "shutdown.exe /s /t 0" to shutdown, it will reliably load the next time you start up.
I was forced to fix it this way because my Dropbox was on the encrypted partition, and Dropbox would complain that it couldn't find the folder anymore (same with Google Drive and SkyDrive, only worse).
This might fix that problem, but I haven't tried it yet (http://www.askvg.com/fix-windows-8-restart-and-shutdown-problems-by-disabling-hybrid-shutdown-feature/)