I did install it from Preferences and the symlink was created by Textmate. It would appear that the mate executable would be at /Applications/TextMate.app/Contents/Resources/mate.I even tried to change location to /usr/local/bin but that doesn't work either.
I wonder if this is a Lion related issue.