Why am I getting a "package could not be registered" deployment error on Windows 10 UWP?

I have an application targetted for Windows 10 and the UWP. The application correctly runs for x86 and x64 but when I try to run it on a mobile device targetting ARM on a Nokia Lumia 820 I get an error message during deployment:

DEP0001 : Unexpected Error: Package could not be registered. (Exception from HRESULT: 0x80073CF6)

There are other questions relating to this error that suggest it could be an issue with shared user certificates or that you can't have Audio and Device use in the same background task but I am not using either of these. There is also a suggestion that this may be due to a missing icon however to the best of my knowledge I am including far more icons than I actually need.

I have tried removing everything from my assets folder and removing it from the manifest but this also hasn't solved the problem.

Edit I've also tried creating a new blank universal project and that too runs on x86 and x64 but not on the mobile.

You have to run Windows 10 Mobile on your Lumia and you should at least have OS Version 10.0.10240.x. This will work with the release Version of Visual Studio 2015. If you have a CTP or Preview Version of Visual Studio, you should update them to release to get it running.

To get the preview onto the phone, you need the Windows Insider app on your phone and follow the instructions. Choose "fast ring" to get the latest bits. http://windows.microsoft.com/en-us/windows/preview-download-phone

Get the app here: https://www.microsoft.com/de-de/store/apps/windows-insider/9wzdncrfjbhk

This should make it work for you.

For more info on the current preview version check this link: http://blogs.windows.com/bloggingwindows/2015/08/12/announcing-windows-10-mobile-insider-preview-build10512/