Well thanks to this guide and about a dozen others I finally got a build submitted. Not sure what I was doing wrong for a long time, I was doing pretty close to what the OP described. It might be because I was signing everything individually instead of with the --deep tag.
Some other issues I encountered (as a Mac noob).
During initial setup, whether certificates or otherwise, make sure to lose sudo a lot. I got some red herring errors that just had to do with permissions.
If you're like me and your using VMWare or similar as a Mac machine, you'll be able to do builds just fine, but you won't be able to test any game that uses Stage3D. I ended up renting a mac2 instance through Amazon ec2 (65 cents an hour, minimum one day), which was its own nightmare.
I might do another post to say whether all this was worth it, this was by far the hardest process to get an app onto an app store. I sincerely doubt my free to play will get the organic installs it needs to be worth the headache.