I would start by restarting the phone (fixed multiple problems when I ran into this problem). I would also verify time/date is correct on the phone roughly. Be careful when looking at some GCM code online as a lot of the code contains deprecated functions.
After that, I would implement retry logic as shown below on my 3G/4G Scenario.
If you are on 3G/4G:
Errors in the 500-599 range (such as 500 or 503) indicate that there was an internal error in the GCM server while trying to process the request, or that the server is temporarily unavailable (for example, because of timeouts). Sender must retry later, honoring any Retry-After header included in the response. Application servers must implement exponential back-off. Troubleshoot
If you are on Wi-Fi:
Note: If your organization has a firewall that restricts the traffic to or from the Internet, you need to configure it to allow connectivity with GCM in order for your Android devices to receive messages. The ports to open are: 5228, 5229, and 5230. GCM typically only uses 5228, but it sometimes uses 5229 and 5230. GCM doesn't provide specific IPs, so you should allow your firewall to accept outgoing connections to all IP addresses contained in the IP blocks listed in Google's ASN of 15169.