Need more information is the 1st thing I'd ask. Second would be are they using their own implementation or "ours"?
Next I'd start by segmenting the working users and non-working to see if there are any clear differences for a 'quick fix'.
I also would make sure I'm monitoring the API Server every 3 minutes from 3 locations across the U.S.A with something like WebsitePulse and also something like New Relic. WSP can be configured to monitor certain protocols so I'd also monitor HTTP / HTTPS as well as monitor them on the server-side, as well as network monitoring, and overall server latency monitoring.
If it's intermittent issues -- does that mean it works sometimes and not others with the same code or is it intermittent with various software that we can nail down to being a software issue on their side?
I've done this exact thing as we've written APIs for large news papers all over CA to use.
I took the response from a more software centric approach. If you're using pre-made software an all if it's 100% the same I'd jump to the user segmentation, and New Relic data to "see" what's really going on, and run network tests between the user and server.
If the API isn't already I'd also make it start recording date/times of all requests, and request my users submit trouble tickets with the date/time of the issue so we can check the log files for activity during that time.
I'd love to hear a more 'network centric' approach at troubleshooting this.