Yes, it notes Windows 2000, but XP is based on 2000 and the clue is there.

Your post didn't reveal much about your "format" or machine but if I were to format the hard disk oddly or a boot virus was still there the message seems proper.

Did you try the XP CD only method to prepare the drive? Is the BIOS Virus protection disabled?

"a MS knowledgebase article saying you can have this problem if you have too many partitions (ie. no letters left to assign to CD drive)."

Very interesting, but your post is far too light on machine and more details.