We are always getting "Invalid Application-ID or API key" when we submit a simple saveObject() request

Our application ID is “WX4E3U3A16”, we are not able to successfully submit requests. We have verified that the application ID and the ApiKey that we are submitting are correct, we are using our Admin key.

Any suggestions?