blockchain.info may not accept compressed keys yet. So maybe that's why it think it's invalid.
I just swept a private key to Blockchain starting with 5K, also says all formats are supported in the import/export section.
Try importing a private key that starts with a K or L. Here, I'll use an example:
L1TU3ksw7CmMbT3JsVnSbCRUM7siEuUvo45ee9BjjMeCYYDtdiQA
Kyoy4Ji5yJqYXaohP6j9CD61YxZp7KrD3ps2N53PtrXdvTN6Pc6j
KxxHV1fNHUt9TB5rf3oag2kSkFowgqwXdZ23zPEzicRvQMxFs9K7
I just generated those from bitaddress.org
Keys that start with 5, including 5K are uncompressed keys.
Yea, I wouldn't know how to do that. I make my paper wallets on bitaddress.org with their brain wallet sections and just back up the private key in import format..