Sim, isso deve funcionar e funciona para mim:
$ openvpn --config loopback-client --tls-cipher TLS-DHE-RSA-WITH-AES-256-GCM-SHA384 --tls-version-min 1.0
Thu Jan 29 00:13:13 2015 OpenVPN 2.3.6 x86_64-unknown-linux-gnu [SSL (OpenSSL)] [LZO] [EPOLL] [PKCS11] [MH] [IPv6] built on Dec 16 2014
Thu Jan 29 00:13:13 2015 library versions: OpenSSL 1.0.1f 6 Jan 2014, LZO 2.06
[...]
Thu Jan 29 00:13:13 2015 Control Channel: TLSv1.2, cipher TLSv1/SSLv3 DHE-RSA-AES256-GCM-SHA384, 2048 bit RSA
Thu Jan 29 00:13:13 2015 [Test-Server] Peer Connection Initiated with [AF_INET]127.0.0.1:16000
Thu Jan 29 00:13:14 2015 Initialization Sequence Completed
Isso está usando os arquivos de configuração padrão loopback-server e loopback-client fornecidos com o openvpn. Certifique-se de adicionar tls-version-min 1.0
(ou 1.2, se você quiser impor isso) às configurações em ambas as extremidades. Fora isso, eu não fiz nada de especial.
O problema é especificamente o AES-256? Ou seja, você obtém o mesmo comportamento com TLS-DHE-RSA-COM-AES-128-CBC-SHA vs TLS-DHE-RSA-COM-AES-256-CBC-SHA?