It's not obvious, but on that same site for the logo, there's a link for getting a cert at a significant discount. I seem to recall it was $100 instead of $500? And that's from Verisign. Took a client of mine through it and getting the cert was the easy part of the process :-)
Update: this page http://msdn.microsoft.com/en-us/windows/ff718579.aspx makes it clearer:
Submissions for the Compatible with Windows 7 Software Logo Program will only be accepted through Winqual. To establish a Winqual account for your company (a prerequisite for creating user accounts), you must establish your company’s identity using a VeriSign Certificate. There are two VeriSign certificates supported by Winqual for creating company accounts...
Basically you must have a Verisgn cert of some kind, but it doesn't need to be a code signing one. You can use a $99 one just to prove you are you, and then buy your code signing one from anyone in the PDF you can download from http://support.microsoft.com/kb/931125 (it appears to include Comodo). Or you can buy your code signing from Verisign and cover both bases. This is also where you can find the link to the $99 first year offer.