Having not seen your attack and not knowing the make-up of your party, I cannot comment on whether or not it should have succeeded. The CR of creatures/encounters in the immediate vicinity of the Titanium range from about 20 to the mid-40's. Not all CNR is guarded by stronger foes than would be "normal". In the case of Titanium and other high-level CNR (mithril, emeralds, rubies, yew), yes, the guardians can be quite a bit more of a challenge than the other creatures around.
To use another example, things like the Mithril chamber were balanced for a group of mid-20th level characters.
One other comment: Many of these guardian creatures have a "weakness" or at least a form of damage against which they are not highly resistant (or immune). Taking only a few points of damage off this guy per hit may indicate that there is a better way to combat them. My disclaimer there is that I have not personally been part of such a fight, nor have I inspected its stats very closely, but even so, just getting "stronger" may not be the answer. In Clarissa's case, for example, golems typically are not easily hurt by bladed/slashing/piercing weapons.