I'm not going to recommend a brand. I'm going to recommend that you decide what type of photography that you want to do and look for a camera system that meets your needs.
As an example, I shoot a older Pentax *istD (upgrading to a k10d soon). Until recently there were no Pentax lenses longer than 200mm. If I were a wild life shooter that would seriously hamper my photography. There are aftermarket lenses longer than 200mm that work fine, but if you want to stay within you camera brand for lenses it's something to think about.
Any recent dslr is capable of taking stunning pictures. For me it comes down to lens selection, accessories, and ergonomics.
Ergonomics? Yep. How a camera fits your hand and where the controls fall are a major factor in how you'll take pics. If you feel like you're fighting the camera all the time you won't enjoy it and your pics will suffer for it.
For me Canons have never felt particularly good in the hand. Pentax is great, closely followed by Nikon. You owe it to yourself to handle as many cameras as you can before you buy.
Just dont get caught up in the megapixel marketing campaign... that not nearly as important as you may think, especially once you leave the point and shoot realm.
Neither of the low end Canon's or Nikon will have a good resale value if a year or 2 down the road you want to upgrade (if you decide its even necessary).
For example, I would chose d40 over d40x, the megapixels arent worth the extra cash. The lense selection will be more than enough for you until you outgrow your camera. If you do outgrow it, skip the d40x and go to the d80, the nice VR lenses that you have acquired during your d40 years will work fantastically on it.
The idea of going straight in to a 800 to 1000 plus dollar camera for a complete beginner is absolutely ridiculous. Yes, we all know they are better, but give me a break. Thats like saying you want to learn to play guitar, and then going out and buying 2000 dollar Les Paul.