Noticed this same thing. I restored my old 3G backup to my new 3GS and the Voice Memo icon was gone. I hadn't reinstalled any of my apps yet, so it was just the vanilla aps that come with the phone. However, if I go to spotlight and search for it, it shows up, the icon is just missing from the home screen. Not a HUGE deal. I am sure that apple will fix this in a future update.
edit: Nevermind, once I re-installed my apps, it just showed up again. Strange, the Voice Memo app must be marked as a 3rd party app for some reason.