When I go to appengine.google.com/a/mydomain.com i am able to login and see all my apps and administer them.
However, when I try to use the remote_api the same username/password does not work.
I'm using the interactive console code from http://code.google.com/appengine/articles/remote%5Fapi.html
I've come across the same issue while developing for GAE on google apps. To make it work, I've created a simple wrapper around a snippet provided by Nick (blog.notdot.net - I can't seem to find the proper reference right now) that has been working for me. You can find it here.
This is a known issue with Google Accounts authentication. If you created an app and set it to use Google Accounts for authentication, and you yourself use a Google Apps account, you will not be able to authenticate against your app as an administrator using that account, even if you've created a Google Account for that email address. The workaround for now is to create a gmail account and add it as an administrator of your app, using that whenever you need to authenticate against your app as an administrator. You can still use your existing account for deployments and to log in to the admin console.
It's a pain, I know - I run into it every day myself.