Apparently it happens from time to time, there are some posts about this problem on StackOverflow. No answers though.
We tried many things, including resetting our secret. It's working now, but it's hard to tell whether our actions had any effect.
It's a bit frustrating with no reaction from Instagram/Facebook and not even an entry on the status page.