I had that problem with my iPhone for a long time. I had to do some digging on my router to fix the problem.
I had to clone the mac address of my computer to ensure a stable connection from my modem to the router. Don't know if it was necessary, but I turned protected mode on for my wireless and have it broadcasting b, g & n with both 20/40 mhz.
I would suggest looking into the settings for your router and try messing around with some of them. My iPhone used to take a little bit to show wifi connected after unlocking, and even then I would have to turn airplane mode on and off to actually be able to use my connection otherwise I would get the no internet connection message.
After messing with the settings wifi pops up as soon as I unlock my phone and it appears to be much faster than it used to be.