This is actually acknowledged by Oracle as a bug in Rel 12. The fix is coming in August patch bundle. As a workaround do the following:
1. Go to Manage Features by country or territory
2. Set the selected extension to Payroll for the country for which you are creating the payroll
3. Create the payroll. It should not error out
4. After payrolls are defined, change the extension back to the appropriate ones.
Hopefully that helps.
Regards