You've specified a fairly generous budget, which gives you a number of options.
Some general advice...
Anything from 6-10 megapixels will be fine. The extra pixels are there mostly for camera firm marketing departments
With DSLRS, the initial kit purchase is usually only the start of the slippery slope into the money pit

The 'kit lens' supplied with most models is moderate wide angle to short telephoto. This will be no good for extreme closeup (macro) work, or sports, wildlife etc. Extra lenses can be as little as 60 quid, but depending on the type of lens, you can usually expect to pay £150-£350 (or a LOT more in some cases) per lens to add extra capabilities to your camera. If your 1000 Euro budget is IN TOTAL, then consider carefully if you might want to save some cash for extras.
With your budget you could either blow the whole lot on a midrange camera+kit lens, or opt for an entry level camera and set aside some cash for expansion.
Incidentally, I'm one of the Nikon fans, so I'm biased in that direction. We've got Canon, Pentax and Sony fanboys/girls as well, so we kind of balance each other out fairly amicably
In the midrange, you've got the Canon 400D, Nikon D80, Sony A100, and Pentax K10 as obvious chocies.
Your entry level choices would be the Canon 350D, Nikon D40 or Pentax K100D.
As previously advised, go out and handle a few - DSLRS vary considerably in size, weight, build quality and ergonomics, The screens and viewfinders also vary in size and brightness. For example, if you like small and light cameras with simple controls, you'll like the Nikon D40. If you're lusting after a 'proper camera' - big, sturdy with lots of buttons - try the Nikon D80 or Pentax K10.
As Pirate says, some brands (eg Sony and Pentax) offer more bangs for the buck - particularly since they offer in-camera image stabilisation. Nikon and Canon are trading on superior body and lens quality, (and huge market shares) and insist on using the (allegedly) superior in-lens image stabilisation. Us Nikon/Canon fans (aka mugs?) pay a premium for for this but are happy in the knowledge that the extra cost is worth it
Regarding the D40 lens issue specifically(must start cutting and pasting a standard repy!)...
The D40 autofocuses with:
All Nikon Kit lenses
Nikon 55-200mm VR (VR= Vibration Reduction) £230
Nikon 70-300mm VR £320
Nikon 18-200mm VR £465
Nikon 105mm VR Macro £480
Sigma 30mm f1.4 £240
Sigma 10-20mm £280
It doesn't autofocus with the cheaper macro lenses, or the Sigma macro/zooms, which are very popular with people on a tight budget. You also miss out on the low light zooms and primes. The Nikon AFS 200mm and 300mm consumer zooms are pretty much the best on the market though, so a D40+kit lens+Nikon 70-300VR wouldn't be a bad way of spending 1000 euros