First of all, I personally would never ever buy one of the small Canon's. I find the ergonomics very bad. The grip is too small and the camera feels all plasticky and toylike. It has improved on the 550D, but still. You'll need to buy a grip to have anything resembling a comfordable handling. Either Nikon of Pentax does this a lot better. I'm a Pentax guy, so I'd buy the K-x in an instant. But I must say the Nikon D3000 looks like a very charming camera to me as well. I don't like the ergonomics of the small Sony's as well, so they're not an option for me...

If any, I'd probably go for the 1000D. Why? It leaves me with the most cash to buy lenses. That extra $200 is enough to get a Tamron 17-50mm f2.8 instead of a crappy Canon 18-55mm. I don't care about 18 megapixels. I never print that big and all they do is slow down Photoshop. So the cheapest one it is.
Or if your budget is big enough, think about a Canon 50D. It such a completely different camera than the small ones. The ergonomics are great which really makes you wonder who they let design the xxxD and xxxxD series.

But this is important:
I would never buy a camera soly based on advice given on the internet!
I don't like the ergonomic of the 550D, maybe you do. Maybe you'll find it the best invention of the world after sliced bread. Who knows. You've gotta try the all out and find what works for you. What I've said is my opinion, and you've got to find your own. Any camera on your list makes great pictures, if in the hands of the right photographer. There is no bad pick!

Hope this helps. Don't worry, I can write crap about any given camera...

[Edit]Oh and thanks for including the European designations. The whole 'rebel' thing confuses the crap out of me... :P