Weird.  Is it an XP machine?  
Yes. 
If so, I'd suggest running different
Could be a directx bug (or windb).
What is pyshell?
What?
The Python is 2.5.4.   
I'm assuming display is the one that failed... but maybe it's not...
and it's decided it doesn't like that mode?
>>> pygame.display.init()
>>> pygame.display.list_modes()
>>> pygame.display.init()
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    pygame.display.init()
error: No available video device
Ian