I've got a small back pack and had a midi shoulder bag, had to get rid of the shoulder bag as the new camera is a little bit bigger than my old one (d70).
Its a shame because i really liked it, they are very hard wearing and lots of little pockets just a bit too thin for the new stuff so got a domke f4 as a replacement.
but seeing as you have a 400D which is roughly the same size as a d70 you should have no problem.
(this is all based on the original green type not the newer black ones)