I use black melamine frequently in my shop. Most of the local hardwood supply houses only stock it in a Particle board core, although I have obtained it with an MDF core on one occasion. I recommend you find out where your local woodshops get their hardwoods and plywoods from, and then check with those suppliers. Try the yellow pages under hardwood. Also check with the local plastic laminate suppliers [suppliers to commercial trade], as some of those stores stock melamine as well.
Painting Melamine is not a good idea due to adhesion. One mght as well just paint MDF.
If you can't find black Melamine [and Egads at that above quoted price, it should be no more than 25 bucks], consider using black plastic laminate over MDF [vertical grade would be fine].