The biggest fear for API providers is to get stuck maintaining deprecated API versions or support some kind of retro-compatibility for them, while the biggest one for API consumers is to see API implementations change and break their client implementations. As an API consumer, I always fear that one day an API provider may just decide to change his API or release a new version that would break my applications (and usually that happens at Chrismas Eve).
Basically API consumers are worried about facing the most common scenario in the computer/software industry, that is: implementations always change. So you're an API provider and you have released an API that other developers are consuming right now, but you can't substantially update it because you're worried to break their client implementations and make them angry with you.
You probably need an API versioning strategy. Let's start migrating.
Last month I had to change my phone number, it meant that I had two phone numbers on two separate phones that I always carried with me. I then started to give my new number to my closest friends that I meet everyday, but that wasn't enough because all the other people still used to call me on my old number. And that was a problem. Basically every time someone texted/called me I asked to delete the old number and switch to the new one. Eventually after one month all the people I really cared about were texting or calling me on the new number, so I could just shut down the old one. What I did was to gradually migrate my friends to the new phone number and then deprecate the old one. I think that this could be a viable strategy for updating an API as well.
A good roadmap would be to release a new API version, but still keep maintaing the old one. This means that while developers find some time to update the clients, their implementations will still work with the old API. Regularly notify them (email, sms, add warning boxes to the documentation) and track those who have already migrated and those who are still using the old version. Give to them some reasonable time, 2/3 months or maybe more, to migrate and then just gradually shutdown the old implementation. Developers probably don't want to keep consuming a deprecated API, so as soon as they found out that a new version is available they will take all the necessary steps to migrate to the new one, just give them a good time window. In the meanwhile you'll basically support both versions at the same time (and maybe, if needed, have two different, but parallel, infrastructures up and running).
There are different strategies for keeping two different API versions running at the same time. You could use different DNS endpoints for each version, or properly route requests by reading the submitted Accept header. I would focus on one API version at a time, so I wouldn't keep the old one running forever.
For more resources, I would suggest reading the first answer of this Stack Overflow question: http://stackoverflow.com/questions/389169/best-practices-for-api-versioning
While for a nice workflow using the "Accept" header, I would suggest taking some inspiration from this implementation: http://files.zend.com/help/Zend-Server-Community-Edition/api_versioning_negotation.htm
