"fresh out of college you probably don't have a AAA game under your belt" - you don't need a AAA game. There are many other levels of game which yield useful experience. As you say, side projects are useful, but so are small indie releases, or mobile games, or internships/work-experience placements/etc.
"most Designers start in QA." I don't think that's true, except at big places like Ubisoft perhaps. For a start, not every company even has a QA department (sometimes because they outsource it to publishers, or simply because they are too small).
Everyone will give you different advice about getting into game design because the role of a designer differs from company to company. (I've even worked at places that didn't employ designers at all.) What I would recommend is this: if you're passionate enough about game design to be willing to relocate to get a job, do whatever will get you the broadest and most impressive portfolio in the next few years. That is probably a game design degree, providing you can find a university with a high quality course (and all the caveats other people have mentioned apply there). A Computer Science degree will help you get a job as a programmer, but won't necessarily let you transition to designer later. But it will pay better, and give you options outside of the games industry.