unable to instantiate application - ClassNotFoundException

For Android Studio:

Build --> Clean Project

Fixed issue.

There are two possibilities. Either you, like me, have a spelling error in your manifest file. Have a co-worker or friend read it to make sure the name is correct. Or you have not referenced the project correctly.

The official document describes how to properly link projects in its documentation.

Why it would first seem to work and later stop working is a bit of a mystery. However, I guess that the VM might still have had the necessary references ready to resolve the classes in the library just fine. A restart of the VM removed all those references and trying to resolve them was unsuccessful.

Update: Regarding the edits in the OP: As you confirm that you have correctly referenced the other project, you can check if the project is included in APK, just to be sure. You can rename and open an APK as any other archive (.rar works fine for me). Sometimes, it happened to me, the project is not correctly included in the APK. A cleaning of your workspace usually remedies the problem and so could a restart of your IDE depending on what you are using. To manually conduct a clean in Eclipse for example, use Project->Clean... or try Android Tools->Fix Project Properties by right-clicking on your project.

As you seem to also have fixed the problem by restarting your device, it could be that the libraries were linked incorrectly. A problem that I have never seen myself but as a very common quote says: "Have you tried turning it off and on again?".