This issue is also impacting me. I'm on a pretty fresh install of Tumbleweed (v 3.38.2). I'm not sure whether this is relevant, but I am running pop shell on my install. 

I originally posted this issue to the forum: 
https://forums.opensuse.org/showthread.php/547890-quot-Prepared-update-not-found-quot-error-on-boot?p=2989238#post2989238

The linked forum post references similar issues occurring on other distros, which seem to indicate this is a problem with `gnome-software`.

Created attachment 844497 [details]
gnome-software log with GS_DEBUG=1

Yes, since a couple of weeks g-s does not work anymore. It apparently never downloads and prepares anything and immediately jumps to Restart & Update which fails.

I disabled g-s autostart, attached is log of GS_DEBUG=1 gnome-software. It starts, refreshes repositories, tells me there are updates, when I switch to Updates tab I am offered Restart & Update (which cannot be true as nothing was downloaded yet); pressing it results in mentioned error.

It seems g-s decides whether to activate Download or Restart&Update buttons based on size of updates to download. Unfortunately debug output does not cover this part of code at all.

Below are also current g-s settings

bor@tw:~> gsettings list-recursively org.gnome.software | sort
org.gnome.software allow-updates true
org.gnome.software.auth account-id ''
org.gnome.software check-timestamp int64 1608096823
org.gnome.software compatible-projects ['GNOME', 'KDE', 'XFCE']
org.gnome.software download-updates-notify true
org.gnome.software download-updates true
org.gnome.software enable-repos-dialog true
org.gnome.software enable-shell-extensions-repo true
org.gnome.software external-appstream-system-wide false
org.gnome.software external-appstream-urls @as []
org.gnome.software filter-default-branch true
org.gnome.software first-run false
org.gnome.software free-repos @as []
org.gnome.software free-repos-url ''
org.gnome.software install-bundles-system-wide true
org.gnome.software installed-page-show-size true
org.gnome.software install-timestamp int64 1606666397
org.gnome.software nonfree-software-uri 'https://en.wikipedia.org/wiki/Proprietary_software'
org.gnome.software official-repos @as []
org.gnome.software online-updates-timestamp int64 1608096844
org.gnome.software popular-overrides @as []
org.gnome.software prompt-for-nonfree true
org.gnome.software refresh-when-metered false
org.gnome.software review-karma-required 0
org.gnome.software review-server 'https://odrs.gnome.org/1.0/reviews/api'
org.gnome.software screenshot-cache-age-maximum uint32 2592000
org.gnome.software security-timestamp int64 0
org.gnome.software show-nonfree-prompt true
org.gnome.software show-nonfree-ui true
org.gnome.software show-ratings false
org.gnome.software show-upgrade-prerelease false
org.gnome.software upgrade-notification-timestamp int64 0
bor@tw:~> ll /var/lib/PackageKit
total 44
-rw-r--r-- 1 root root 40449 Nov 29 19:13 offline-update-competed
lrwxrwxrwx 1 root root    45 Aug 22  2018 transactions.db -> ../../../usr/share/PackageKit/transactions.db
bor@tw:~>

Created attachment 844618 [details]
journalctl for system boot when updates were prepared

(In reply to Andrei Borzenkov from comment #2)
> 
> I disabled g-s autostart, attached is log of GS_DEBUG=1 gnome-software. It
> starts, refreshes repositories, tells me there are updates, when I switch to
> Updates tab I am offered Restart & Update (which cannot be true as nothing
> was downloaded yet); pressing it results in mentioned error.
> 

And when I booted this VM today it started performing offline update. I attach system log in case someone can spot something useful there.

(In reply to Andrei Borzenkov from comment #3)
> 
> And when I booted this VM today it started performing offline update. I
> attach system log in case someone can spot something useful there.

Comparing system and user logs.

g-s log (time is likely in UTC)

05:33:52:0937 PK  role now update-packages
05:33:52:0941 Gs  emitting global waiting
05:33:53:0405 Gs  emitting global querying
05:33:53:0852 Gs  emitting global installing
05:33:54:0132 Gs  emitting global downloading

system log

led from uid 1000
Dec 16 08:33:54 tw.0.2.15 packagekitd[1714]: DownloadProgressReportReceiver::start():http://download.opensuse.org/tumbleweed/repo/oss/ --kernel-macros;5.9.14-1.2;noarch;openSUSE-20170729-0

g-s log

05:34:04:0493 Gs  emitting global finished
05:34:04:0501 Gs  not GsPlugin error pk-engine-error-quark:1: GDBus.Error:org.gtk.GDBus.UnmappedGError.Quark._pk_2dengine_2derror_2dquark.Code1: Prepared update not found: /var/lib/PackageKit/prepared-update

While PackageKit continues

Dec 16 08:33:55 tw.0.2.15 packagekitd[1714]: DownloadProgressReportReceiver::start():http://download.opensuse.org/tumbleweed/repo/oss/ --libgstreamer-1_0-0;1.18.2-1.1;x86_64;openSUSE-20170729-0
Dec 16 08:33:55 tw.0.2.15 packagekitd[1714]: DownloadProgressReportReceiver::start():http://download.opensuse.org/tumbleweed/repo/oss/ --libldap-2_4-2-32bit;2.4.56-63.1;x86_64;openSUSE-20170729-0
...
Dec 16 08:35:24 tw.0.2.15 PackageKit[1714]: update-packages transaction /16_aebbddec from uid 1000 finished with success after 91423ms
Dec 16 08:35:42 tw.0.2.15 PackageKit[1714]: daemon quit
Dec 16 08:35:42 tw.0.2.15 systemd[1]: packagekit.service: Succeeded.
Dec 16 08:35:42 tw.0.2.15 systemd[1]: packagekit.service: Consumed 45.318s CPU time.

So apparently GNOME Software somehow does not understand that PackageKit needs to download packages and and prepare (offline) update and does not wait for it to finish.

(In reply to Andrei Borzenkov from comment #4)
> 
> system log
> 
> led from uid 1000

Sorry it should have been

Dec 16 08:33:52 tw.0.2.15 PackageKit[1714]: new update-packages transaction /16_aebbddec scheduled from uid 1000

Seems to be a packagekit issue, since doing pkcon offline-trigger also gives the same error:

> pkcon offline-trigger 
> Command failed:
> GDBus.Error:org.gtk.GDBus.UnmappedGError.Quark._pk_2dengine_2derror_2dquark.Code1: Prepared update not found: /var/lib/PackageKit/prepared-update

(In reply to Atri Bhattacharya from comment #6)
> Seems to be a packagekit issue, since doing pkcon offline-trigger also gives
> the same error:
> 
> > pkcon offline-trigger 
> > Command failed:
> > GDBus.Error:org.gtk.GDBus.UnmappedGError.Quark._pk_2dengine_2derror_2dquark.Code1: Prepared update not found: /var/lib/PackageKit/prepared-update

offline-trigger does not create this file so the error is correct. This file is created by

pkcon --only-download update ...

And this is exactly the problem with gnome software - it calls (equivalent of) "pkcon offline-trigger" before updates are downloaded.

(In reply to Andrei Borzenkov from comment #7)
> 
> offline-trigger does not create this file so the error is correct. This file
> is created by
> 
> pkcon --only-download update ...
> 

To illustrate

bor@10:~> ll /var/lib/PackageKit/
total 4
lrwxrwxrwx 1 root root 45 Jul  5  2020 transactions.db -> ../../../usr/share/PackageKit/transactions.db
bor@10:~> pkcon -d update
Getting updates               [=========================]         
Finished                      [=========================]         
Updating packages             [=========================]         
Refreshing software list      [=========================]         
Resolving dependencies        [=========================]         
Installing updates            [=========================]         
Downloading packages          [=========================]         
Finished                      [=========================]         
bor@10:~> ll /var/lib/PackageKit/
total 8
-rw-r--r-- 1 root root 212 Jan  8 13:19 prepared-update
lrwxrwxrwx 1 root root  45 Jul  5  2020 transactions.db -> ../../../usr/share/PackageKit/transactions.db
bor@10:~> cat /var/lib/PackageKit/prepared-update 
[update]
prepared_ids=openSUSE-2021-28;1;noarch;repo-update,openSUSE-2021-29;1;noarch;repo-update,openSUSE-2021-30;1;noarch;repo-update,openSUSE-2021-31;1;noarch;repo-update,openSUSE-2021-33;1;noarch;repo-update
bor@10:~>