I finally got it to work by starting over from scratch. I think the problem was that when I went to a new computer and uploaded a new certificate I had to revoke the old certificate. It seems that once it's revoked that maybe it can't be used again.
So I recreated my signing certificate, recreated a p12 file from it, recreated (modified) the app profile (making sure to select my certificate again and selected all of my devices again), redownloaded the mobile provisioning file, reselected these in the iOS configuration screen and restarted Flash Builder and it worked again.
I had tried to use a wildcard, "com.myactualdomainhere.*" and I couldn't get that to work but I didn't do all the steps above (I didn't recreate my signing certificate) and if you can't reuse a certificate then that may have been the issue.
So I did all the steps above and used the app name, "com.myactualdomainhere.MyApp" and made sure it matched in the application descriptor file (for AIR apps) com.myactualdomainhere.MyApp.
It would be nice if someday they could simplify this process and give better error messages. Maybe they could verify the different parts along the way, for example, "your certificate is ok, your app profile checks out, but your app id is incorrect."
Also, MilkyWay posted a link to a post that has some more helpful information.