Spatial awareness and proprioception are highly underestimated in my opinion. The thing that has helped me out the most when practicing land nav is just being able to really focus on the terrain, and understand where I am in relation to other terrain features in the area (terrain association). This is much more difficult to do at night, but with practice, you will get better and better at it.
What has NEVER helped me with land nav is just burying my head into my map and compass, and attempting to just stay on one single azimuth for miles. That always messes me up.
Ultimately, think of just becoming a general outdoorsman. How does a creek sound when you are standing on the opposite side of the hill adjacent to it? How do different types of earth (dirt, sand, rock) feel under your feet and how do you relate that to what you see on your map? How do smells change as you enter different biomes, and what does that mean?
By using all of your senses in a combined effort, you will essentially become "in tune" with nature, and navigating will become that much easier.
I know its been awhile since your original post, but hope this helps you or someone else.