My 98 E300 did this once in while as well. Same routine - the car preglows, the accessories come on, but no cranky on the starty. Pulling the key and trying again always did the trick.

Changing the battery won't help. The battery only powers the remote locking/unlocking functions. Starting the car is a separate thing. Gilly, I think, has posted some discussions on how the electronic key operates.

- JimY