It's probably just some fractal noise with varying distributions constructed from multiple noise layers with different seeds and then integrated using blending modes. At least it looks "mathematical" to my eyes, not like a natural texture. The Clouds, Noise and Dither filters are your friend...
Adding to what Mylenium said, was this actually done in Photoshop? (Maybe in Photoshop and something else?) This could easily be done in, say, Ambient Design's ArtRage program. One could easily create a texture of their own using the natural media in that app and then bring it over to Photoshop for some final touches.
Yeah, the background could be just a mix of layers, there are parts of it that look very hand painted to me. The shading on the foreground element also looks hand shaded.
This vintage stippled look is quite a popular style at the moment in animation / motion graphics. Would be great if anyone knows of any nice PS brush packs that could help me along.