[Nexus One Themes and Apps] Chahk:
Cleared cache, dalvik-cache, market data, market cache, manually deleted /system/app/Vending.apk, /data/data/com.android.vending, /data/dalvik-cache/system@app@Vending.apk@classes.dex.

Then I tried flashing the "Vending-2.2.6-signed-testkeys.update.zip" from recovery. After accepting the conditions it FCs in 2-3 seconds. Same if I simply try to push the Vending.apk over the old one (from recovery or otherwise), or do "adb install -r c:\Vending.apk". Fix Permissions from ClockworkMod recovery doesn't help either.

Here are the relevant logcat entries:

...
D/vending ( 1265): [29] LocalAssetDatabase.notifyListener(): 1930517786221093583 / INSTALLED
E/vending ( 1265): [29] LocalAssetDatabase.updateFromReconstruct(): 103 changes to local DB!
...
D/GoogleLoginService( 397): onBind: Intent { act=android.accounts.AccountAuthenticator cmp=com.google.android.gsf/.loginservice.GoogleLoginService }
...
E/vending ( 1265): [29] 1.run(): Fatal error from server: Sent a bad request.
W/vending ( 1265): [29] AsynchCheckForNotifications.onException(): Server error on CheckForNotificationsRequest: com.android.vending.api.FatalCommunicationException: Sent a bad request.
...
E/DatabaseUtils( 397): Writing exception to parcel
E/DatabaseUtils( 397): java.lang.SecurityException: Permission Denial: writing com.google.android.gsf.settings.GoogleSettingsProvider uri content://com.google.settings/partner from pid=1265, uid=10005 requires com.google.android.providers.settings.permission.WRITE_GSETTINGS
E/DatabaseUtils( 397): at android.content.ContentProvider$Transport.enforceWritePermission(ContentProvider.java:348)
E/DatabaseUtils( 397): at android.content.ContentProvider$Transport.insert(ContentProvider.java:196)
E/DatabaseUtils( 397): at android.content.ContentProviderNative.onTransact(ContentProviderNative.java:146)
E/DatabaseUtils( 397): at android.os.Binder.execTransact(Binder.java:288)
E/DatabaseUtils( 397): at dalvik.system.NativeStart.run(Native Method)
W/dalvikvm( 1265): threadid=23: thread exiting with uncaught exception (group=0x4001d7e8)
E/AndroidRuntime( 1265): FATAL EXCEPTION: Thread-33
E/AndroidRuntime( 1265): java.lang.SecurityException: Permission Denial: writing com.google.android.gsf.settings.GoogleSettingsProvider uri content://com.google.settings/partner from pid=1265, uid=10005 requires com.google.android.providers.settings.permission.WRITE_GSETTINGS
E/AndroidRuntime( 1265): at android.os.Parcel.readException(Parcel.java:1260)
E/AndroidRuntime( 1265): at android.database.DatabaseUtils.readExceptionFromParcel(DatabaseUtils.java:160)
E/AndroidRuntime( 1265): at android.database.DatabaseUtils.readExceptionFromParcel(DatabaseUtils.java:114)
E/AndroidRuntime( 1265): at android.content.ContentProviderProxy.insert(ContentProviderNative.java:408)
E/AndroidRuntime( 1265): at android.content.ContentResolver.insert(ContentResolver.java:592)
E/AndroidRuntime( 1265): at com.google.android.gsf.GoogleSettingsContract$NameValueTable.putString(GoogleSettingsContract.java:55)
E/AndroidRuntime( 1265): at com.google.android.gsf.GoogleSettingsContract$Partner.putString(GoogleSettingsContract.java:126)
E/AndroidRuntime( 1265): at com.android.vending.compat.MarketCheckinHelper.updateCheckinDatabase(MarketCheckinHelper.java:12)
E/AndroidRuntime( 1265): at com.android.vending.CheckinUpdater.sendContentSyncViaCheckin(CheckinUpdater.java:219)
E/AndroidRuntime( 1265): at com.android.vending.CheckinUpdater.performCheckin(CheckinUpdater.java:176)
E/AndroidRuntime( 1265): at com.android.vending.CheckinUpdater.access$000(CheckinUpdater.java:38)
E/AndroidRuntime( 1265): at com.android.vending.CheckinUpdater$1.run(CheckinUpdater.java:109)
E/AndroidRuntime( 1265): at com.android.vending.util.WorkService$1.run(WorkService.java:37)
...

I have a feeling that the new version requires Google to specifically enable it for your specific device, and no matter how many times you try (re-)installing it it just won't work until they flip the switch on their end.