Can not Final process an employee and rehire him effective next day

Hi ,

Due to our Business process we need to terminate and final process an employee effective 13- DEC-2013(  pay period end date ) and re hire him in  a different job  effective 14-DEC-2013( Middle of the new payroll  pay period) .   This is not an issue usually, except for this one person, we are not able to create a new hire record, we get the following message

APP-PAY-07193  You can not continue with this change future person type exists .

There aren't any future person types, when queried from the back end. We also made sure there are no future payroll actions. Still Unabe to re hire him.