I've never tried backing up to an encrypted HFS+ drive myself, so I'm not sure what would happen if I did, but from the message you are getting it sounds like TimeMachine doesn't want to use the encrypted drive, and is trying to decrypt it, which takes time. It is possible that the drive is currently decrypting and TimeMachine should start working once that is done. I answered another question about that here.
So you don't have to click the link, this is what I said there:
If you type the following command in Terminal you will get all sorts of info on all the corestorage volumes currently attached to your Mac, including the conversion status you are looking for:
diskutil cs list
There are more answers here.
One of my favorites is Nick Bedford's answer towards the bottom of that page that gives you just the status of each volume without all the other info.
diskutil cs list | grep -e "Conversion" -e "Volume Name"
If my theory is correct, once you have run that command if you scroll down a bit you should see:
Encryption Status: Unlocked
Conversion Status: Converting (backward)
which means the drive is being decrypted. If TimeMachine is not working because of the encryption then it should work again once that process is complete. If you have nothing on the drive and want to 'speed up' that process then you can reformat the drive as a normal HFS+ journaled partition, without the encryption turned on and then trying Time Machine then.
I'm not sure the encryption is the problem, but the error message seems to indicate that it is, so I am curious to see what the status is on the encryption and conversion status of your core storage partition, and if waiting for the decryption to finish/reformatting fixes the problem. Good luck!
Best Answer
Yes, they can. You can back up as many machines as you want with the same disk.
Just make sure you have enough space on the drive left. As far as I'm concerned you also don't have to fear one Mac deleting the old backups of another machine in case you run out of space. Time Machine will only delete old files from the machine it's currently running from.