You must use OAuth2 authentication, API key alone is not enough as you must authenticate as a Google Apps super admin or delegated admin (with appropriate rights) in order to perform Admin SDK Directory operations.
My project, Dito GAM was recently updated with full support for Admin SDK calls. It makes use of most (all?) Directory API calls. See:
https://code.google.com/p/google-apps-manager/source/browse/trunk/gam.py
Also, if you notice bugs or ambiguities in the Google documentation, be sure to report them. It won't get any better if someone doesn't tell them about it! Use the "Report a bug" link at the bottom of all developers.google.com pages. It's very simple to use and pinpoint the exact issue.