As provided, it works for me:

#!perl -l
$_ = '<key>Album</key><string>1963 - The Lightning Fingers of Roy Clar
+k</string>';
s/(<key>Album<\/key><string>)\d+\s*-\s*/$1/ ;
print;
# outputs: <key>Album</key><string>The Lightning Fingers of Roy Clark<
+/string>
[download]

Are you trying to do multiple replaces at once? If so, you need need s///g;. If that's not it, could it be a character set issue? In any case, it's usually much better to use parsers than regexps for HTML and for XML.