Creating transparent glass with an image texture w/ alpha channel
I found a solution to your problem. The answer lays within the lightpaths. You want your direct rays with your texture and alpha and your indirect (Colored shadows) using a solid blue object. This can be done fairly easy inside the nodes.
So, this shadow:
With this texture: 
This is your solution: 
One material will be used when rendering the cube and the other one when rendering the shadow. The Lightpath node will output white when the ray is directly coming from the object to the camera. Black if it isn't.