This sounds entirely believable to me. The flow of thought must have been something as follows:
Microsoft product marketing:
"We have to name the Xbox follower - let's call it Xbox 2."
Consumer studies expert:
"Nah, we can't do that, since it will seem older than PlayStation 3 to those dumb consumers"
Xbox brand manager:
"How about Xbox 3?"
Microsoft product marketing:
"We can't call it Xbox 3 since that would raise questions about a missing second one"
Xbox brand manager
"Ok, let's have an agency create us some different routes of names."
Agency
"We came up with three main routes:
1. Xbox + number(s), for example "Xbox 247"
1. Xbox + Word, for example "Xbox Evolution"
2. Xbox + letter combination "Xbox NE""
Consumer studies expert
"Let's study those alternatives with real gamers."
* results arrive *
"It seems that the letters combinations didn't make much sense, since the consumers couldn't understand that they identify a next generation product"
"The word were considered cool, but could dilute the main Xbox brand - for example if the gamers started to talk of 'Evolution' only."
"The numbers were seen as feeling the most technically advanced, and easy to use. There was some confusion about the meaning of the numbers, however."
Xbox brand manager
"Numbers it is, then. So, would you come up with some combination that would be logical and start with 3, to go against PS3?"
Agency
"We came up with the following number combinations having a three in them: Xbox 3000 (the next millenium), Xbox 365 (days of the year), Xbox 360 (full circle), Xbox G3 (generation three)."
Xbox brand manager
"Hey, Xbox 360 is kinda cool, goes with 3D graphics and immersion and stuff. Yeah, we could do some cool rendered shit for that."
Microsoft product marketing
"That's quite ok. And this is an one generation solution, anyway. We can call the next device simply 'Xbox 4' anyway, since it is the follower to 'Xbox 360'. By 2010 no one will remember that there was no 'Xbox 2'"
To simplify - naming follow-up products is a bitch - incredibly complex task where there never is an optimal solution. Some solutions suck more, some less.
Hence, if you ever see a product naming task moving towards your desk, run for your life and don't look back!