I'm getting the same problem recompiling with 0.18.1.... Read thorugh here, and then looked on my machine, and right there in /usr/X11R6/lib is libXrandr like I think it's supposed to be. So, what if you seem to have the randr library, but myth won't link with it?????