It's hard to answer without knowing the average response time of your service. A user accustomed to an average of 4s response time may not be too fussed about a 12s delay; but a user accustomed to 0.1s response will.
It's 10 seconds or less
Anyhow, as indirect answer, you should expect users getting really annoyed after 10 seconds. See this famous post for more.
Just an additional anecdote:
Hey sorry, we think there's a problem with our servers you might want to try later...
You should consider an alternative phrasing for this. A user I may ask: "What do you mean 'you think' there's a problem? Is there or isn't there? And if there is... what is it? What sort of people wrote this system?"
It's a bit like a printer throwing a message such as:
I think I'm out of ink - but maybe not.
Also note that anthropomorphising is most annoying for users when the system misbehaves (see more).
Please speak to your developers - in most client-server protocols, once a request is on its way the only 'right' way to stop it is by a timeout set explicitly by the developer (on the server, client, or both). You can't just show a message as such - you need to ensure the request has been 'killed'. Just a note that you may want to discuss this with the developers before finalising the design.