As a matter of fact, there already IS a Middle-Earth Risk map. See, they kinda made a bunch of LOTR based games when the movies came out (Monopoly, Chess, Risk, etc.). I actually own it, and it's not bad. Now let me see...
Here's a picture of it (sorry it isn't bigger, the site I'm hosting it from has size limits). It's actually rather interesting to play. There are rivers and mountain ranges that divide the map up, with only a few bridges to cross the rivers (mountains require to go around), and sea invasions functioning a little different as well (sea travel is obviously only on the western coast of Middle-Earth, so sea invasions go from a port territory to the next port territory in line, and vice versa). The biggest change is the introduction of fortresses. At certain locations (Minas Tirith, Rivendell, Minas Morgul, Isengard, etc), these fortresses give an extra point to defense and, during a player's reinforcement phase, produce one extra unit on every fortress you control. To counter this, everyone also has a leader unit which gives an attack bonus.
Now, Lackattack, if you want to make a map out of this, I have a full-sized version as well (which the names are easy to read on). If you want, I can email this to you. Alternatively, if anyone artistically gifted (not me, I can't do crap with anything artistic) wants to take a crack at turning this into a workable map, please by all means just ask and I'll email the full-sized to you as well.