See that forum:
http://transgaming.org/forum/viewtopic.php?t=1325
it writes everything that you need....
I tried prelink -ua, and it had the same messages, that you had too... and i done all that they wrote on this forum, and now the games work for me, perfectly
not the missing dependencies was the problem!!