With complicated regular expressions like that, limiting the amount of back-tracking becomes an important concern. This may be addressed with possessive quantifiers: (?>...), *+, etc. Consider the following version:

use warnings;

$braces = qr/(?<braces> { (?: [^{}] | (?&braces) )*+ } )/x;

s/class \s+ (?<class_name> \w+) \s* 
  (\: (\s* \w*)? \s* (?<ancestor> \w+))?+ \s* 
  $braces
//x;
[download]

Note the possessive *+ and ?+. But this probably does not solve your problem. Are you sure the braces were properly balanced in your input? Could there have been some escaped or quoted brace(s) that failed to match up?