On Ubuntu, one could just do sudo apt-get install prelink but I don't think it's urgent you have prelink installed, unless you plan to run apps that mess with other apps by injecting things into their memory space. I think you're getting ahead of yourself. Have you checked the appdb page for that app, http://appdb.winehq.org/objectManager.php?sClass=version&iId=5661 ? It has a couple hints that might help.
