Usually, that message pops up when you kill an NPC or other humanoid that requires a "black soul gem"...
But, a soul gem has to be COMPLETELY empty in order to hold a soul. Even if a Grand Soul Gem has a lesser soul in it, it can't "fill up" the "balance"...it's potential was simply wasted. So, if you have no empty soul gems, then yes, you'd get the same message...even if some of your gems weren't "full" so to speak. If it has ANY soul in it, it's "full"....
Here's the breakdown:
http://www.uesp.net/wiki/Oblivion:Soul_Gem#Soul_Gems
The important part is here though:
Quote:
If you get the message, "There is no soul gem in your inventory capable of holding such a soul," then you don’t have an empty soul gem big enough to hold it (or you have attempted to capture the soul of an NPC and you do not have any empty Black Soul Gems). There are no partial captures; it is all or nothing.
Once you use a filled Soul Gem it is gone. One notable exception to this is Azura's Star, which is the equivalent of one Grand Soul Gem but is reusable.