Just tested several apps on a couple of devices running Android 4.3 but did not have any problems. This error is returned when your storage is locked for the android system and deployed APK can't unpack. This usually happens when device has SD card and it is mounted as USB storage to the PC. Can you verify that your SD card is accessible on your device i.e. use a file manager program and try to save/copy a file on it (e.g. image).
On a side note, you can try to build your application in "Release" and check if it works on your device. Use Graphite, right click on your solution in "Project Navigator", select "Build Settings" and select "Release". Delete the app from the device before trying to deploy again. This would verify whether the problem is SD Card/ Internal Memory related.
Do you enjoy Icenium? Vote for it as your favorite new product here (use short code H048S).
Looking for tips & tricks directly from the Icenium team? Check out our blog!
Share feedback and vote for features on our Feedback Portal.