YEAH!
Okay, since FR is fairly 'typical fantasy world' it shouldn't be TOO hard to get a sense of what is normal...have a few adventures where they're hearing about famous people, growing up, fighting some enemy, etc. Sort of a mini-campaign of an adventure or three long, shouldn't be too hard to establish what the world is like (e.g.: not drastically different from a typical homebrew/fantasy world).
After that...I believe things go boom. I think it'd be cooler if it was something they didn't know about, rather than something people already know is dangerous...where's the fun if they already know about it.
===
So beneath the desert there has lurked ruins that no one has been able to uncover...not nessecarily for lack of trying, but because they try, and go a bit mad once they get too close...
Meanwhile, the head of the Red Wizards has been looking with an eye toward this area...great power, great magic, a foothold in ancient ruins, it's all too tasty to pass up. so he finds a way to reach it by going through the Plane of Shadow.
He dissappears for several weeks. The Red Wizards go crazy covering it up, making it seem like nothing's amiss.
And then he comes back, no different than before.
And starts some great plan/mission.
Now, to the PC's, this is just another fight against an evil wizard type. Only, when they interrupt his great ceremony, maybe finding a way to off him, maybe just providing a distraction while Elminster and Drizzit go in an whip things butts (or whatever.

).
At the completion of the ceremony, things are getting drained...even the big heroes are having trouble. But they've weakened 'em. The PC's go up against a HIGHLY weakened wizard (he's been harmed, drained levels, had his Int damaged a bunch, etc.), and take him out.
"You fools...what have you done?"
Only, nothing goes boom...
It's not until people startcasting the healing spells that things start go to wrong...
Using the CoC as a guideline, I assign ability damage to each spell.
The first time Elminster is HEALED, the priest is drained of all his energy and collapses, skeletal, onto the ground...
===
That should make 'em good and scared.
So now I have this 'new magic,' and everything follows it's rules. As people try to see and sense the weave, it's still there, but there's something on the other side...something hungrily feeding off of every spell cast in the world.
So, rationally, you do some research...try to uncover something...only tomes and the like seem to share this...even magic items will feed off of their wielders, if nothing else than with sanity (which I could introduce, not as nessecarily something to go mad from sights, sounds, etc., but mad from the 'magic of the mythos', so to speak).
Have the PC's go on another adventure or two where the natural world is turned on it's face. I love the image of dragons falling from the sky -- any supernatural or spell-like power does sanity and/or ability score damage. Maybe Elminster isn't insane, but Mystra and any other dieties of magic most definately *are*. And the big E isn't far behind.
The more you know about how this happened, the more you succumb to it.
It's amazing what the simple removal of magic can do to the world.
But I need BIG things, too. This is a stubtle threat, more terrifying than horrifying (more 'uh-oh! Oh, crap!' and less 'AAAUGH! I'M GONNA MESS MYSELF!')....I need BIG terror. I need things that start to REALLY hurt things.
So, where to I go from here? A ritual has summoned enough of the Mythos-power to make magic a VERY dangerous thing...how do people react to this?
(I think I'll also have some of the magic mutate things instead of simply damaging their ability scores or rendering them insane...things which have become so normalized to magic, like with a beholder's flight).
Okay, things are starting to gel...keep it going, I think I'm nearly there.