When a new API key is created and allocated to you (when you create a new account or renew your API key) it can take up to 15 minutes for this key to be available for use worldwide. 

This is similar to DNS propagation, where it takes a certain amount of time for a change in address to be recognised across all the international networks.