I'll give this a shot, but I'm not the best teacher ;)
The echo command is only going to print to the output buffer. Think of the output buffer as a place on the server's memory where you build your whole chunk of output stuff, including your normal HTML rendering statements. It doesn't actually get sent back to the browser until you tell it to when your script ends, PHP header() functions, etc. Therefore, writing *stuff* out via echo sits in the output buffer until this happens. Then you tell the server to sleep for a bit, and redirect with a header(). You're probably getting an error message too, correct?
You're message, "All Done!", is not going back to the browser. It is going to print the "All Done!" to the output buffer (not send it back to the user), sleep for 5 seconds, then redirect the browser to the location specified in your header function.
Try mogwai's suggestion to see if meets your desired results. You may also find the Output Control Functions [us3.php.net] to be a bit enlightening.