Actually just checked my original PM, which did have line breaks, and the problem turned out to be that when I copy the signature from the PM and paste it into bitcoin-qt, an extra space appears in the middle of the signature.  No idea why.  This causes bitcoin-qt to report that the signature could not be decoded.  Simply deleting that space from the signature allows the message with blank lines to verify.  Sucks that I lost a day with my miners because of this, but there are worse things in life.