This post in the Steam Community Forums helped me solve the issue:
You want to manually delete the Steam Linux Runtimes and then reinstall them (probably only the latest, but I deleted all 4 of them)
Enable show Tools in your Steam Library
Search for runtime
There were 4 of them installed 1.0 to 4.0
Find the App IDs for each: right click -> properties -> updates tells you the App ID
where ever you have your Steam games installed: for me this was ~/.steam/steam/steamapps/
delete the corresponding appmanifest_{App-ID}.acf files
in /steamapps/common/ delete the 4 SteamLinuxRuntime folders
restart steam and redownload the 4 runtimes by searching for them in your library
This fixed the issue for me