What you're suggesting is likely good enough, and very likely far more secure than just about any other lock on your house.
If the only hash function you can find is MD5, go with it, but make sure to HMAC with the passphrase as the key. Again, it's not going to be the weak point of your security. I'm sure I could pick the lock on your front door faster than I could break an MD5 HMAC. Obviously, HMAC-SHA1 would be better, or SHA-256, even. See if you can find a SHA-1 for Arduino.
I don't understand the exact protocol you're proposing. Why the timestamp and a counter? Either alone would work fine, assuming you take more than one second to do the protocol. It doesn't hurt to do both, but let's break it down:
Client sends a request to open.
Server sends a unique string to the client.
Client computes HMAC(passphrase, unique-string) and sends the HMAC back to the server.
Server also computes the HMAC and compares them. If they match, the door opens.
That seems good enough to me, the only thing we're debating is the content of the unique string. A timestamp alone would work if you prevent replays. You could do that by having the Arduino spin until the clock ticks. But there's also nothing wrong with an equivalent of:
static int counter = 0;
...
sprintf(challenge, "%d-%d", time(0), counter++);
send(challenge);
and that would be unique enough.
The risk in this basic protocol would be someone pre-computing an appropriate HMAC. Strictly speaking, the timestamp and the counter helps thwart this, but in practical terms it isn't really going to help. If someone intercepts any given successful challenge and response, they can run a dictionary search on passphrases to find the right HMAC.
But still, it's almost certainly more secure than the locks on the other doors.
Jon