Got it solved by editing the iOS Distribution Provision Profile in the Developer Member Center.
For some reason there were 2 certificates to choose from for the Distribution Provisioning Profile. I switched over to the other certificate and I could Validate and Submit my Archive build for beta testing.
So, you may have more than one certificate for signing your Provision profiles. Make sure you have the right one (by trying all of them) and hopefully that should work.
I tried many things like Exporting Developer profile from Xcode Accounts and importing it in the organizer, installing the provision profiles from the member center, adding them to my keychain. But none of those worked. It started working only after editing the appropriate Provisioning Profile manually.
You could also trying removing all your available Provisioning Profiles and let Xcode create new ones for you. This will work too.