I know I'll most likely get ticked off here because I'm not actually providing the solution, but I am part way there and perhaps we can help each other to find it.
I have this very same problem running i3 on Crunchbang 11 (based on Debian stable). The problem for me is that notifyd (or is it i3?) is picking up a background image from my currently selected gtk2 theme and tiling, as opposed to stretching, that image to draw the bubble background when, as far as I can see, it should be doing neither. I mean, this happens no matter which notifyd theme I select, the config files for ALL of which specify a PLAIN background. I have looked at my xfce4-notifyd.xml file and also in the config (gtkrc) files for all of the notifyd themes I have installed, and I can find no command nor any reference whatsoever to notifyd using image files for its background. I didn't even think it was possible lol.
Just in case it gives you a clue, in my case it looks like notifyd (or is it i3?) is using a panel_bg.png or button_bg.png image from my gtk2 theme folder (I can't tell which as they are very similar). Your screenshot leads me to believe that the same thing may be happening with you Tony? Selecting a different gtk2 theme results in the correct (plain) backgrounds being displayed by notifyd, so the problem seems to be gtk2 theme specific even though I can't for the life of me figure out why.