You can't copyright trivial work so the size of the spec matters.

It depends on how you create your server. If you go to their website, look at their API, and start typing identical code then that's not ok. It's pretty clearly copying. If you do black box testing and then write your own API that's fine. It's clearly not copying but a new original work.

And what criteria should be used to tell when an API is complex enough to be copyright-able?

Generally, anything can be copyrighted as long as it's sufficiently original. The phrase “I have abandoned my search for truth and am now looking for a good fantasy”, for example, is under copyright by Ashleigh Brilliant, who own a case against a t-shirt manufacturer using it.