I'm actually on the same shoes more or less with you. I've had my 400D since the day it came out in stores, and I was always a firm believer of good lenses instead of the body, that's why i invested a lot of money on good glass. But the noise control of the XXXD bodies isn't up for it when it comes to wildlife. I too have to use ISO800 for bird photography, and I rarely do it. I prefer the hit and miss of slower shutterspeeds at ISO400 than the amount of noise I get from higher ISOs. In that respect, the consencus is that the XXD range is definitely better in higher ISO-less noise. What I'm not sure though is whether to go for the 40D or the 50D. I've read the article on dpreview about the 50D and it said that the 40D has less noise than the 50D, due to the pixel density. But, having the possibility to crop your photos from a 15MP one is a great advantage for better reach for those small timid birds.
I think you'll definitely see a great improvement when it comes to ISO, so I think you made a great choise.