Windows Me isn't the best OS arround.
I got a p3 666 and the game works well on 800x600.
You have any suspicious programs running in the background?