Are you getting either of these messages?
"No Devices Registered" message
This message appears if no device has been setup with your MobileMe account and Find My iPhone is turned on. If you still have the device in your possession, set up Find My iPhone in Settings > Mail, Contacts, Calendars > MobileMe.
"Your device is no longer locatable" message
If you see this message, Location Services (or Find My iPhone in iOS 3.x) was turned off on your lost device*while*you were using the app. You will not be able to locate your device anymore, but you can still display a message on its screen, have it play a sound, remotely lock it, or remotely wipe it.