I think the 'too much textures' effect is because the rest of the map is so vibrant... You have really bright, 'cartoony' colors, which look awesome in a clean-cut map that doesn't pretend to be drawn on paper. The paper texture just looks a bit alien under colors like that.

The map itself looks very interesting and well thought-out and the combination of symbols&font look great together.