What you have experienced is not a problem - it is the way Photoshop works. To increase the responsiveness of the program cached data may be used. Histograms based on the image cache display faster and are based on a representative sampling of the image - think a lower resolution version of the working image. Hence the pixel count will be inaccurate.
If what you are doing is simply a measurement then consider changing your preference setting to use uncached data. Go to Preferences > Performance > History & Cache and change the cache levels to 1 (no caching). When you are done with your measurements change the cache level back to its typical value (4) or you will experience some performance issues with normal work.
What does "representative sample" really mean?
The funny thing is that for some areas (circles for example) the number in the Histogram was very accurate, but complex shapes were horriblly inaccurate (off by about a factor of 4-5). The complex areas involved combinations of other smaller circular areas, so have trouble understanding why these areas would be so far off compared to circles. None of the areas in question were rectangular, but some sides of the regions did have one or two straight edges along with the circular other edges.
Anyway, glad to read that it's a known issue and there is a way around the problem to get at an accurate number.
Thanks for the suggestion - will keep that in mind for next time I do this.
The sample used is some sub-sampled version of your image, that is, a low resolution version.
You should be aware that if such anaylsis this is an important aspect of your work you would benefit from having the Extended version of Photoshop, which has numerous measurement capabilities. You could, for example, have several areas selected and take a measurement which would provide you with the areas of all the selections plus their combined areas as well as numerous other data. All these data can then be exported to a spread sheet for additional analysis.