Some further thoughts on this.
Maybe you can still use normals, but try adding fresnel (or variable)
reflection.
Have a look at this photo: http://www.benzor.com/misc/desert.jpg
Part of the colouring and look of the sand appears to come from actual specular
reflection.
-tgq
