I've figured it out. Unfortunately, after far too many blogs and articles, I've discovered this problem can only be fixed by reinstalling completely, and not selecting virtual environments on the software addition section.
Problem was, even though I have a intel processor, Parallels Desktop doesn't yet support PAE (under most circumstances).