Step one is to ensure you have removed the 64bit version correctly. Microsoft provide a FixIt tool for your use here.
From this point Microsoft support suggests the following for this error, which seems to have solved the problem for several people there:
Try to install Office 2013 and check for results. If the issue persists, then restart computer in Windows Clean boot following these steps and then install Office 2013:
Press the Windows + R key on the keyboard.
In the Run windows type MSCONFIG and click Ok.
Click the Boot tab and uncheck Safe Boot option.
On the General tab, click to select the option Selective Startup, and then click to clear the option Load startup items check box.
On the Services tab, click to select the Hide all Microsoft services check box, and then click Disable all.
On the Startup tab, click Open Task Manager. In the Task Manager window under startup tab, right click on each startup item which are enabled and select Disable.
Click OK, and then click Restart.
Source
EDIT: As you can imagine I cannot test if this method works as I am not suffering the same issue. So do let us know the result.
UPDATE: There are older examples of this situation which might help you provide an answer. This has come from a Microsoft support post on an older version of Office, which you can find here
