It takes a little time even when everything is approved.
- My binary was approved.
- My In-App Purchase (IAP) was approved.
- My In-App Purchase was Cleared For Sale.
- Testing the purchase in development with a sandbox iTunes Account worked great.
- Purchasing in production with a real or sandbox iTunes Account would fail.
I didn't have to wait long, something like a couple hours and it just started working.
Now, my binary and my In-App Purhcase were approved at the same time and almost immediately after they were both approved, I released the app version to the store.
I'm not positive, but what I probably should have done was wait a couple hours before releasing that new app version and give the In-App Purchase a chance to "register" or "propagate" in the Production App Store.
Just a recommendation for others.