3dsmax? Try it with Global Super Sampling on or off. If its the low poly intersecting with the high. Select the low poly just before you bake, go into element mode and hide all (in the edit poly modifier). This will leave just the high poly and your cage when baking and fixes the intersecting MentalRay AO issue.
post your app and renderer dude, its completely pointless making people guess. If your using Mentalray make sure your working at roughly real world scale and your transforms are reset. I get the black dots in max sometimes when im baking very similar meshes, usually a push modifier with a low value fixes it.
Make sure you're checking the actual file it saves not what is displayed in the render preview window. What is shown in the preview window is a "complete bake" and what the actual files look like. So check the file you specified in the "File Name and Type" field. The preview window is so annoying that some people turn it…