How do I calculate the maximum plain text length allowable for a certain cipher text length? I am encrypting and storing sensitive values in the database. I have a set max length in the database, but in order to provide useful user feedback, I'd like to know the max input I should allow for a given database length.

I can throw together a test that brute forces an answer, but I'd like to understand more generally how to go about calculating.

In my specific case, I'm using Twofish in CBC mode with PKCS7 padding. The result is stored as base64 encoded string. The database column is a VARCHAR(512) column.

I know base64 has an overhead of about 137% of input so, roughly, 512/1.37 = ~373. 
But now where? is 373, which happens to be 23 blocks, the maximum size, or is there more to it?  

Thank you very much for you patience. :)
Well, to figure out this sort of thing, it's easier if we work backwards.

So, we start at the back (the fact that we can store up to 512 characters in a database field), and consider how much binary data we can store.  Well, base-4 takes 3 bytes of binary data, and encodes it in 4 bytes of base-64.  Thus, we can store 3*(512/4) = 384 bytes of binary encrypted data in 512 bytes of base 64.

Now, once we can store up to 384 bytes of encrypted data, we need to consider how much plaintext that corresponds to.  Well, you don't specifically mention an IV; in this situation, we might guess that the encryptor selects a random 16 byte IV and sets the first 16 bytes of the ciphertext to that.  The second thing to consider is whether the encryptor adds a message authentication code; that is a cryptographical check value that will allow you to detect if someone else modified the database field.  Now, you don't mention that you have one, so we'll assume that you do not.  This gives us a ciphertext region of 384-16 = 368 bytes.

Lastly, you mention that you use CBC mode with PKCS7 padding.  CBC mode always generates a ciphertext that's a multiple of 16; 368 is already a multiple of 16, so we don't loose any room there.  In addition, the length of the ciphertext is exactly the length of the padded plaintext; you mention PKCS7 padding, which always adds at least 1 character of padding; this gives us a final value of 367 bytes of plaintext which can fit.