The paint color metaphor was used a while ago during Brexit debates, when "sources" suggested that indicative votes "will leave us with an Auf Wiedersehen, Pet Brexit'". Auf Wiedersehen, Pet is an old TV show about seven British construction workers. In one of the episodes they pick a color to paint their shed by making lists of preferences. The winner is yellow, which no one wanted, but some marked as a second choice. The story ran in major UK newspapers with headlines like Daily Mail's May Warned She Could End up with an 'Auf Wiedersehen, Pet' Brexit No-one Wants:
"They told the paper: 'There is a scene in Auf Wiedersehen, Pet where the builders pick a colour to paint their shed and end up with yellow. 'They are all baffled because no-one voted for yellow, but it turns out that two people put it down as their second choice. 'So there is an issue with a ranking system, as it comes with the inherent danger that you end up with a result that no-one wanted.'"
The "indicative votes" were supposed to produce an outcome by a sequence of votes to choose among, roughly, hard Brexit, soft Brexit and no Brexit. So this is what is being illustrated. But is it paradoxical? I think not. An outcome that nobody likes but can live with is the definition of compromise, not something unexpected. And in the OP example the builders are "worse off" compared to what? Painting both houses their color? But that was never in the cards.
What really happened during Brexit is closer to the Condorcet (a.k.a. thwarted majorities) paradox of preferential voting, where roughly a third of population supported each option, so that there was always a majority to reject every option. And, depending on sequencing the "indicative votes", any option could have been arranged to win. Fishburn and Brams discuss other paradoxes of preferential voting, but Auf Wiedersehen, Pet does not really display any of its paradoxical features in particular.
Nor does it have a catch that makes social cooperation games with rational but inferior outcomes interesting. The most famous is the prisoner's dilemma, but arguably closer to Auf Wiedersehen, Pet is the stag hunt. There each player has to choose to hunt a hare, which they can do on their own, or a stag, for which cooperation of the other player is required. As in preferential voting, the players do not know the other's choice. The "safe" option leads to the inferior outcome with two hares and no stag. Except in Auf Wiedersehen, Pet, we end up with the stag, if the hares mean getting their favorite color for their house, and the stag is an analog of yellow. Whether it is or not depends on how much they dislike their house being yellow vs their neighbor's house being red or green. But either way there is no clearly superior alternative to create a paradox.