Most blocks are just grey on maps

Well I don't really agree with that. It may not be a bug in that blocks are misidentified, but it certainly is highly inconsistent. Why have a separate colour for clay, for example, one of the blocks you're hardly ever really looking for nowadays, and a separate colour for wood, but make obsidian the same as stone? Or why make mushroom blocks, pumpkins, dandelions and roses all green?
With there being 14 base colours and 56 actual colours (of which 14 are duplicates anyway), this doesn't fit with the 8bit/binary style of numbering everything else has, and is clearly unfinished or meant to be expanded. Originally maps only had 1 zoom level, but with the option for more built in. That shows the maps were not yet completely done when they were released. This too simplified palette obviously needs to be expanded.
So, no bug, maybe, but inconsistent behavior and clearly not fully done.

How the maps are currently implementied is per se reasonable (mineral blocks grey, natural blocks green etc) and thus intended.
Surely it can be done other way / better, but this a point for the the MineCraft Forums: Suggestions.

Nobody reads suggestions on the MineCraft Forums

The implementation results in inconsistency, for example, all ore storage blocks are light gray except lapis, which is dark gray. Block.blockLapis is Material.stone, while the other storage blocks are Material.iron. The only difference between those materials is the map color, and both are otherwise identical to Material.craftedSnow.

If materials have been added solely to allow differentiation in map color, e.g. between dirt and grass, stone, snow blocks, and ore storage blocks, etc. (which is likely since map color is the only difference between them); it seems reasonable to expect a new material to be created for mycelium, obsidian, pumpkins, sandstone, etc. to give them the appropriate map color, or decouple map color implementation from materials altogether and assign the appropriate colors to blocks more directly.

Note: Names are referenced according to MCP's interpretation of the obfuscated code. The original source code may have different and/or more reasonable names.

It would be nice to just have all the rgb colors, but that probably won't be implemented before 2.0

"How the maps are currently implementied is per se reasonable" - Not if you build with bricks. I want my brick house to look red on the map, not dark gray. There already is a red map texture (albeit light red), just move brick over to that from the much-too-large stone section. Or, while your at it, actually color the map based on the block colors in the default texture pack. I don't see how this is anything but a bug. Just because it is the way things currently work doesn't mean it shouldn't be fixed (all bugs that are currently in the game are the way things currently work), I see this as something that is definitely wrong with the game (inconsistency between world and maps) that should be fixed.

I agree. They should make sandstone yellow, and not gray.