A full console dump would be useful for troubleshooting this issue, but I think what the clients are experiencing is due to either a misconfigured fast download server, or it being not in sync with the game server.
Normally there are two server variables that are set to 1 by default:
I assume they are at their default values, and I suggest you to check the server.cfg and the relevant gamemode config files that reside under the cfg folder of your server installation. You'll probaby need to connect to the server via an FTP client. The relevant config files should look something like this:
You should check each of these files (whichever exist) for the sv_downloadurl server variable. It should be set at the lowest level possible, ie. server.cfg and you also need to make sure it isn't being overwritten in a higher level config file. What I mean is, it could be set correctly in server.cfg but then overwritten in gamemode_casual_server.cfg etc. It should point to your fast download server where the map files are stored in bzip format. It should look something like:
After making sure this variable is set, you should upload all the map files compressed with bzip2. The files will have an extension bz2 after you compress them, such as:
However, if you're using a game hosting provider, there probably is an easy to use synchronization tool in their control panel that will provide you with the option of compressing and uploading the newly added map files over to the fast download server, so I suggest you check the control panel for this option first.
Once your fast download server is in sync with your game server (it contains all the map files that the game server is running), the clients should be able to download any map they don't have locally from your fast download server as soon as they connect.