That usually means that you unknowingly passed it the wrong image version:
https://community.fly.io/t/postgres-flex-database-postgres-has-a-collation-version-mismatch/14391
Try the “Identifying your Postgres image version” step again. (It’s easy to overlook something!)