Scheduling the testing effort can be tricky. If you schedule testing too late, the development team won't have enough time to react to critical issues found by the test team. If you schedule it too early, the test team will flood the team with bugs that are related to incomplete features. How do you decide? The truth is that testing is always present in some form throughout the life of the development cycle. At the very beginning, a senior tester should be involved in giving feedback about the game design, machine requirements, and development schedule. Most of the testers I know are quite sensitive to game design issues and can be invaluable in creating a brand new game or refreshing an existing title. Many of the luminaries of the industry started their careers in testing, so take advantage of their expertise. In fact, the guy that started the company I work for used to be a tester for Origin Systems.
When the game design document is in final draft, a few testers should be assigned to the product for a month to create the test plan. You'll be surprised how many potential issues they'll find having nothing more than some PDF files and notebook paper. Usually their feedback will be used to tweak the design document before it gets laminated.
The first usability test can actually occur before the first build. The sketches of the user interface design can be presented to usability testers in the place of an actual build. This is especially important when the development team is curious about different design directions of a user interface or tutorial. Of course, someone will have to be in the testing room interacting with the tester since there is nothing more than sketches on the table! The other rules still apply, of course. Don't give the subject any clues about how something is supposed to work.
At some point the development team will begin submitting builds to a small test team whose main focus will be to check the build against the milestone acceptance criteria. The initial builds will have tons of broken code and missing features, which is why you want a small test team until a critical mass of working code begins to emerge. The small test team is working on functional tests at this stage. The test team grows in step with the development effort, reaching a maximum size as the team reaches the milestone before code complete. This is an excellent time to submit a good build for a full test suite: playability, usability, stress, and configuration. In the best of all possible worlds, you'll want to run each of these tests once just before code complete, and once just before content complete. This will give the development team some assurance that they've made some improvements to the game based on the first full test pass. It will also ensure they haven't broken something important.