While this is bad news for the rover, the metal apparently was also used in several Air Force aircraft, which may put people's lives at risk.
The titanium problem may force a mission delay beyond 2011 (next launch opportunity would be 2013): "Engineers may not finish testing on MSL's titanium until the the middle of next year, leaving little time to replace the metal if it does not meet specifications."
In more bad news, even without this problem, the mission's costs are increasing again and possibly up to another $115M above the previously allocated $400M to cover new problems. The article discusses that somewhere between the currently supplied $32M in additional funding and $115M, NASA may have to delay or cancel another mission to raise the funds. A delay of the launch until 2013 would presumably require even more funds.
Resources: Spaceflight Now article http://spaceflightnow.com/news/n0910/20titanium/index.html