Make sure you have Receive Transparent checked for your map's material, if that is not checked the receiving material will only render shadows at full strength.
In the properties panel under the Material tab beneath the Shadow heading check the Receive Transparent check box.
Receive Transparent (quoting from the manual)
Allows this material to receive shadows whose intensity is modified by the transparency and color of the shadow-casting object
In the case of a smoke simulation, it will definitely will have intensity, or alpha less then one.
The image below is an example:
Without Receive Transparent on the left and with Receive Transparent checked on the right.
I changed the Receive Transparent on only the ground plane, the object casting the shadow does not need it checked unless it too will receive a transparent shadow.