Tracking lost iPhone with iCloud

Hi everyone.

OK so let me start by telling you that this is my first post and that I'm somewhat a newbie when it comes to the iPhone.

I never really tried to understand what MobileMe was about, but when I installed the iOS5, I agreed to use iCloud and enable the GPS tracking device of my phone (Unlocked iPhone 4 using a T-Mobile SIM).

Now comes the obvious part : I lost the damn phone.
I'm pretty sure it slipped out of my pocket while riding a cab, but this is of no importance.
I tried finding my phone with the iCloud Find my iPhone website but, even though when I called the phone it seemed to be ringing, iCloud told me the phone was offline.

So here comes my question : is this normal?
Does one need to have an iPhone actually using data to be found online, or can a regular, locked, idle iPhone could be found online by iCloud?
Is there the possibility that I did something wrong when activating iCloud?

I am sorry if an answer to this has already been posted somewhere, I did a quick look-up within the forum and via google and couldn't find anything (am I the first guy to lose an iPhone with iCloud installed?).
I also apologize for any mistake in my English as I am not a native speaker, hope you'll be kind to me

Thanks for your help !
I didn't try to locate my phone before I lost it, but my contacts on iCloud were blank, so I think I didn't set it up properly...
If I don't get any new news from the lost and found, et least I now have an excuse to buy the new 4S