When you deploy a file to a gallery using the File CAML element, SharePoint does not automatically remove the file when you deactivate the feature (or retract the solution). Presumably this is to prevent parts of the site that rely on the presence of that file from breaking if you were to accidentally deactivate the feature.
To get around it, you should attach a feature receiver to the feature that deploys your custom master page. In the "FeatureDeactivating" event, you can take care of removing the file manually. Something like this:
public override void FeatureDeactivating(SPFeatureReceiverProperties properties)
{
var site = properties.Feature.Parent as SPSite;
var gallery = site.GetCatalog(SPListTemplateType.MasterPageCatalog);
if (gallery != null) {
gallery.GetItemById(0).Delete();
}
}