I noticed that if I sign out of the Sandbox Account by Settings -> App Store -> SANDBOX ACCOUNT Sign Out, then the restore will be successful.
Sign out of Sandbox Account through settings.
Remove the app.
Re-install the app.
Attempt to restore IAP by signing in again to the sandbox test account when triggered.
If I do not sign out of the SANDBOX ACCOUNT, then the restore will fail.