Symmetric key in homomorphic encryption over the integers
It turns out that just like the question linked to in the question, the key needs to be an odd number so that the encrypted number doesn't have the same parity (odd or even-ness) as the plain text value.  When it has the same parity, the encryption failed because you can tell exactly what the plaintext bit was!

As for why the high bit needs to be set, I'm going to just assume that it's to make sure the key is large, which helps security.  If someone knows differently, please inform me!