Tim Schafer explained that the reason it was removed was due to the rights to Psychonauts transferring from Majesco to Double Fine. Microsoft policy is that games without licensed publishers aren't allowed on the Xbox 360 (outside of the Indie Games), so it was removed.
Double Fine is working on getting the game back up, but as of this month they've still been having problems since Double Fine doesn't technically meet the requirements to be an Xbox 360 publisher (most notably due to a lack of disposable cash). So even though the game was one of Microsoft's flagship products in the Xbox Originals line, it's no longer available (and likely won't be available again any time soon) due to bureaucracy and red tape.
Update: Psychonauts is back on Xbox Live Marketplace, now published by Microsoft (bringing the game full circle). I also checked on my Xbox 360 to be double sure, and it is indeed back.
Update 2: It seems the game is only available on the Xbox Live Marketplace in North America (thanks Pedgey). Double Fine is aware of this and is working on getting Microsoft to re-add the game in other territories as well.