Ok, it's counting the linebreaks as characters. So If your signature spans a couple lines that would be why. Line 335 of scripts/changebasic.inc.php looks like this:
if ( strlen($Signature) > $config['SIGNATURE_LENGTH'] ) {
Change that, to this:
$lengthcheck = preg_replace("#(\n|\r|<br />)#","",$Signature);
if ( strlen($lengthcheck) > $config['SIGNATURE_LENGTH'] ) {