I could resolve this by entirely removing and reinstalling parallels tools (also make sure the /usr/lib64 symlink mentioned above does exist if it's a 64bit system)
Thanks, Yep using the symlink trick above works. =)
On a side note, sometimes when I mount the parallels tools image, the image gets corrupted.