Well even if the client has Ulib and ULX in his addon directory it wont work...
Correct. ULX/ULib isn't written to run if they have it installed locally and connect to a server.
Too many possibilities for version conflicts.
That's why it's required that the server has it in the download cache, fast (sv_downloadurl) or otherwise.
You really need access to your server console to help us help you.
You would be seeing a ULX (or possibly ULib) error at server startup, and/or when the menu command is run from the client (but would show on the server console).
And when you say new download of ULX, do you mean SVN? Or from our downloads page at
www.ulyssesmod.net?