Well I just tried to open that file, and yep, you get that dialog box ???
The File is not illegal, (The Resolution is to low) so what the prob ?
You can open it in ImageReady CS, Scale it up 2X, Copy to Photoshop CS, and scall it down 50%, so you can get it in without to much trouble.
What other images will it not allow you to open ???