Your Mac is too old to use the Internet version of recovery, and regular Recovery was on the drive you took out.
You will need to Install from your 10.6 snow leopard disc, upgrade it with Software Update until you are running 10.6.8, and only THEN will the Mac App Store appear and you can re-download and re-Install whatever system (10.7 or later) that you were running. You use your "Purchases" page to re-download.
--------
I would just like to add that they are SCUM to not start the install for you in the store when it would be really easy for you, and make you go through these hoops. The Apple Store will generally not do that to you -- they will make sure you got your re-install before you left the store, unless you decided not to do it there. And the Apple Store Wi-Fi is really fast and the downloads are buffered on the store computers in the back.