If x264 does, so does VLC, mplayer, ffmpeg, gstreamer, and dozens of other applications that use video and audio decoders in Linux. Fortunately quite a lot of the world is not the United States, and today VLC is the world's second most popular media player and has never paid one cent in patent licensing fees.

But of course, yes, being open source does not magically exempt you from patent laws in countries with insane, broken patent laws. In practice, if you want to make a large-scale commercial application that will be distributed in the US that uses x264, you will probably need to pay for an MPEG-LA license. They're quite cheap, though: 0 cents per unit up to 100k units, 20 cents per unit after that until 5 million, and 10 cents per unit after that.

Largely, the question of whether a distro contains any particular piece of software is whether the people who run the repositories are willing to host it. This applies both to possibly-patented software, but also to libraries like DeCSS (necessary to play DVDs) that violate the laws in some countries, but not others.