There is also no information whatsoever what key-algorithms are supported, in what length and how they need to be formatted to be accepted. This problem exists for several years now. Lousy support and design I might say!
I found out what BitBucket expects to receive as a valid SSH-Key:
RSA-Public-Keys with a length of 1024 - 4096 and with the following format. Everything is on 1 line, so no carriage-returns anywhere!! And only 1 space to separate the fields. The last space and following date field are optional:
I discovered that an ssh-dsa key I had that was rejected by the UI could be imported from GitHub, even though the Bitbucket UI gave me an "invalid SSH key" message when I tried to add it directly. It worked like a charm once imported. So, I think this is a limitation in the Bitbucket account management UI that ought to be addressed, not just papered over with a better error message. Please look for a followup bug report.