Hello Ben,
Billing state may take several minutes to update. If you're still experiencing the issue, check the following items:
1- On Cloud Console, go to Billing menu and ensure that the billing is completely set up, including a payment method.
2. Open
an incognito session of Chrome, from there login to Cloud Console and try to create a GCE VM instance. If this resolves the issue, the problem could be a caching issue with your browser or proxy server (if your computer is behind of a proxy server).
If the issue still persists please let me know and I'll investigate it further.
Sincerely,