With a little effort they could use ssh keys instead of passwords...
They should ask users to provide their ssh public keys, and use them to give access to a new provisioned server locking down password-based ssh logins. That's how other players (like AWS) do.
For a start they could just use a proper random root password, instead of a default one, and maybe only allow ssh access from the same netblock the install was ordered from.
However, one thing i don't get: Why is it that people don't log in immediately after it is ready? On Linode it only takes a few minutes to (re)install a VM, but GoGrid might be slower of course.
I have used GoGrid for a while. And though originally very critical of them(check my blog) haven't had too many problems lately. For both dedicated servers and cloud servers I've always had a random root password generated. Not sure how this person ended up with one that was g0gr1d.
As for your question, by the sounds of it he ordered a dedicated server not a cloud one. Those usually take them the better part of a day to setup.
That wouldn't help if the backend controlling requisitions is what's compromised (as other comments possibly point to), but you're right, it doesn't sound like these guys have any clue about security at all.
They should ask users to provide their ssh public keys, and use them to give access to a new provisioned server locking down password-based ssh logins. That's how other players (like AWS) do.
This is basic basic basic security stuff.