I don't know what Legg says in your link, but there are variants of the universal prior in which "the coin is fair" has small complexity, because nature has access to random numbers.
You can't have a variant of the universal prior that makes all incoming bitstrings equiprobable regardless of their K-complexity, because that would be the uniform prior.
You're about to flip a quantum coin a million times (these days you can even do it on the internet). What's your estimate of the K-complexity of the resulting string, conditional on everything else you've observed in your life so far? The Born rule, combined with the usual counting argument, implies you should say "about 1 million". The universal prior implies you should say "substantially less than 1 million". Which will it be?
EDIT: Wei Dai's comment explains why this post is wrong.