Failed to install *.apk on device '*': Local path doesn't exist

I'm recieving the following error when trying to run my app on my phone. It used to work, but it has now decided to always give me this error and I can't figure out how to get it working again.

Failed to install *.apk on device '*': Local path doesn't exist. 
com.android.ddmlib.SyncException: Local path doesn't exist. 

Launch canceled!

I've tried restarting the computer, the phone, and the debug mode, none of which have worked.

Edit: I get this error both on my phone and on the emulator!

Why my APK is not installing?

Why APK won't install on Android? First, make sure that your Android version supports the APK version you want to install. Also, remove the Play Store version of the app before installing an APK. Don't forget to check the storage space and permission to install apps from unknown sources.

Ok I figured it out. I had moved the apk file to a different directory (trying to fix a different problem) and eclipse was too stupid to figure it out. As said in the comment below- fix the problem with Project->Clean...