I think the nationalism over different territories would be one of the most fun parts as it would really enhance the role playing of the game. Though I definitely see how it could lead to some troubles, it is after all just a video game and even though I think people would want to own their own country/region, I don't think it would be that big of a problem and would actually enhance the experience.
For traveling on water, an interesting idea is used by the 1257 team. You travel on water the same as you do on land (only faster I think), but you have to go through a "bridge" onto the water. Then when you fight a battle at sea it takes place on a ship map where you fight on the decks.
If Europe wouldn't work though, Westeros from A Song of Ice and Fire as it's a very diverse land similar to Caladria and the books/show is great and it would be interesting to fight over that.
On a quasi-related note: is the mod open source or does chadz have all the source code locked up? I ask wondering if a non-dev could try and make a map so the devs would just have to implement it.