4.0 ice cream sandwich - Not getting current location even if Location Services are enabled

Device: Samsung mobile phone
Android: 4.0.3

My Location Services are enabled, but I am not getting the current location. When I restart the phone, it works.

What could be the problem here?