Update!
I cross-posted my initial post to rec.games.frp.dnd and ENWorld and received some interesting replies.
On rec.games.frp.dnd, Tussock made a few suggestions: first and foremost, he had the idea that the land beyond the mountains was previously ruled by some sort of incredible power, such as a dragon or a demonlord. The creature was defeated recently, allowing for the sudden settlement of the lands. I like this one. I could combine it with my idea of the land being cursed by the gods; the creature could be part of the curse, or perhaps the guardian of the land. Maybe the land wasn't cursed by the gods, but some sort of demon or devil, who was worshiped as a deity. This creature could still be alive and kicking, and doing things to antagonize the new settlers (a possible explanation for the undead, and perhaps a high-level campaign hook should the game get that far).
Tussock also suggested using the humanoids as being analagous to Indians in the Old West, perhaps with a certain group of paladins who insist on enforcing the treaties made with these people. Good idea, as well. I had already been thinking of something along these lines, so that's gold, too. I don't know if Indians are a suitable parallel, as I really want these people to be fallen, but it is quite conceivable that they will receive the same kind of treatment that Indians received during the settlement of the West.
Based on that, I have the following antagonist groups:
1) Bandits
2) Humanoid "indians"
3) The Demon Lord and his undead legions
4) Foreign interlopers
That's a good start, I think. The other thing I will be doing to keep the Old West feel is using the ruins as pseudo-ghost towns. This was suggested by a few people, and also something I was thinking about, so I am going to have that going on, too.
Now, on ENWorld, amidst a great deal of discussion of treant cacti

Whisper72 suggested that the nations who are interested in settling the new expanse should be trying to deal with the local "self-styled warlords." This is also a good idea, and will provide plenty of adventure opportunity. It will also give me an excuse to intensify things like bandit and humanoid attacks.
Another suggestion I liked was MaxKaladin's. He had the idea that there should be some sort of war on the other side of the mountains. Another great idea: it reinforces the Western feel, and provides further explanation as to why the major nations haven't been able to do much about these settlers pouring in without any kind of national allegiance.
So far, I've had a lot of good suggestions, and the situation for the campaing is really starting to take shape. Thanks to all who contributed. Next time, I'll try to take a look at the local campaign area.