[Nexus 4 Q&A, Help & Troubleshooting] anon4129325:
Okay side-loaded these APKs and then elevated them to system level app because I had a feeling it was probably a permission issue since everything was working correctly but giving a generic "failed" message which usually points to a permissions problem.

Anyways PlayStore is working perfectly and I can update / install new apps again so thanks for your help :)

For Google Search's sake I'm going to throw up my LogCat below to help others find this page:

08-25 14:49:42.147: E/ActivityThread(7189): Failed to find provider info for downloads

08-25 14:49:42.157: D/Finsky(7189): [1] 2.run: Loaded library for account: [sF67wNOQNwY7YBqI_AfqNkLsp8M]

08-25 14:49:42.157: D/Finsky(7189): [1] 2.run: Finished loading 1 libraries.

08-25 14:49:42.177: D/dalvikvm(7189): GC_FOR_ALLOC freed 456K, 5% free 11685K/12176K, paused 19ms, total 19ms

08-25 14:49:42.187: E/Finsky(7189): [427] DownloadProgressManager.makeNewCursor: Download progress cursor null: content://downloads/my_downloads

08-25 14:49:42.187: E/Finsky(7189): java.lang.Exception

08-25 14:49:42.187: E/Finsky(7189): at com.google.android.finsky.utils.FinskyLog.wtf(FinskyLog.java:43)

08-25 14:49:42.187: E/Finsky(7189): at com.google.android.finsky.download.DownloadProgressManager.makeNewCursor(DownloadProgressManager.java:126)

08-25 14:49:42.187: E/Finsky(7189): at com.google.android.finsky.download.DownloadProgressManager.onDownloadProgress(DownloadProgressManager.java:234)

08-25 14:49:42.187: E/Finsky(7189): at com.google.android.finsky.download.DownloadProgressManager.access$000(DownloadProgressManager.java:28)

08-25 14:49:42.187: E/Finsky(7189): at com.google.android.finsky.download.DownloadProgressManager$2.run(DownloadProgressManager.java:97)

08-25 14:49:42.187: E/Finsky(7189): at android.os.Handler.handleCallback(Handler.java:730)

08-25 14:49:42.187: E/Finsky(7189): at android.os.Handler.dispatchMessage(Handler.java:92)

08-25 14:49:42.187: E/Finsky(7189): at android.os.Looper.loop(Looper.java:137)

08-25 14:49:42.187: E/Finsky(7189): at android.os.HandlerThread.run(HandlerThread.java:61)

08-25 14:49:42.187: D/Finsky(7189): [1] DownloadQueueImpl.startDownload: Download com.gvoip starting

08-25 14:49:42.187: W/dalvikvm(7189): threadid=24: thread exiting with uncaught exception (group=0x415a5700)

08-25 14:49:42.187: A/Finsky(7189): [427] DownloadProgressManager.makeNewCursor: Download progress cursor null: content://downloads/my_downloads

08-25 14:49:42.187: E/ActivityThread(7189): Failed to find provider info for downloads

08-25 14:49:42.187: E/AndroidRuntime(7189): FATAL EXCEPTION: download-manager-thread

08-25 14:49:42.187: E/AndroidRuntime(7189): java.lang.IllegalArgumentException: Unknown URL content://downloads/my_downloads

08-25 14:49:42.187: E/AndroidRuntime(7189): at android.content.ContentResolver.insert(ContentResolver.java:910)

08-25 14:49:42.187: E/AndroidRuntime(7189): at com.google.android.finsky.download.DownloadManagerImpl$1.run(DownloadManagerImpl.java:47)

08-25 14:49:42.187: E/AndroidRuntime(7189): at android.os.Handler.handleCallback(Handler.java:730)

08-25 14:49:42.187: E/AndroidRuntime(7189): at android.os.Handler.dispatchMessage(Handler.java:92)

08-25 14:49:42.187: E/AndroidRuntime(7189): at android.os.Looper.loop(Looper.java:137)

08-25 14:49:42.187: E/AndroidRuntime(7189): at android.os.HandlerThread.run(HandlerThread.java:61)