I would say your image does look too soft. Your shutter speed is slow for the lens at full stretch but IS should have taken care of camera shake, so long as you were careful, but that won't combat subject movement. However, the softness in your image does not look like blur to me - it looks like mis-focus. Part of the problem is that your shot is somewhat underexposed and the lighting seems very flat and lacking contrast - you did say it was misty! Contrast is a crucial element in creating the perception of sharpness. The underexposure has lost what detail there may have been in the feathers and that also makes things look soft - if you can't see detail in the feathers they will not seem sharp, but really they are too dark to see much at all.
If we look at your image in Lightroom with clipping indicators turned on and the RGB histogram we see that your shadow areas are very blocked up and you have about 2.5 stops of spare headroom in your exposure. There are several areas of the bird that are pure jet black - RGB = 0,0,0 - no detail whatsoever.
For the purpose of comparison I've uploaded an album with a shot of a starling taken with my 40D and 100-400 lens at 400mm, f/5.6, 1/1600 and 400 ISO in good light. It was shot in raw and I have included 100% crop examples with different levels of sharpening, including none at all. Have a look and see what you think. Here's the album (by the way, my example is underexposed by about 2/3 stop and I have lots of featureless black on my bird too
)....
http://picasaweb.google.co.uk/EezyTiger/100400Sharpness?authkey=MPLdKhJb1Ww
Here's one example 100% crop, with no sharpening at all....
and here's how it sharpens up with DPP sharpening = 3 (my usual default)....
You should certainly try a proper focus test before sending the lens in, but you will need a static high contrast flat target, perpendicular to your lens, good lighting, a solid tripod, mirror lockup and a timer or remote release to see what the lens is truly capable of. IS should be off for a tripod sharpness test.
Actually, I've just had a thought - did you give the lens time for the IS to spin up and stabilise fully before shooting? You should hold the half shutter press for about a second before shooting, in order that the stabilisation motors can spin up to full speed. If you shoot before then, all bets are off.