Can't decrypt using pgcrypto from AES-256-CBC but AES-128-CBC is OK

MCRYPT_RIJNDAEL_256 isn't AES-256. It's the Rijndael cipher with a block size of 256 (hence the error). AES is a subset of the Rijndael cipher using block size of 128 bits and key sizes of 128, 192 and 256 bits. This is also reflected in the IV size.

To create an AES-256 encrypted ciphertext you can use MCRYPT_RIJNDAEL_128 with the correct key size (256 bits is 32 bytes). The _128 postfix indicates the block size to be used; you can still use it with any valid key size of 128, 192 or 256 bit.

Beware that mcrypt - especially the underlying C-library - is not maintained anymore. You're better off using the openssl or later crypto libraries.

The mcrypt and OpenSSL wrappers will also happily allow invalid key sizes, only warning you - if you're lucky. That's of course not compatible with about any well defined AES library.