LH 456 on April 26 definitely has availability in everything except F. The First Class cabin is currently full. If you're just trying to get out of Y on that flight, it should be possible. The upgrade options for specific segments online do seem to depend upon married segments, and I've had agents say that a rebooking is necessary when the online option isn't showing or working. Since your outbound is rebooked already, it's probably no longer syncing as a married segment. Just a hunch. Definitely try to cycle through agents to see if one is more helpful, but I wouldn't be surprised if one of them suggests rebooking both directions.