EVP_PKEY_keygen fails on Travis with "invalid operation"

[jeroen.ooms@xxxxxxxxxxxxx (Jeroen Ooms)]

I wrote some simple bindings to generate an ecdsa key:

  int nid = my_nist2nid(curve);
  EVP_PKEY_CTX *ctx = EVP_PKEY_CTX_new_id(EVP_PKEY_EC, NULL);
  bail(EVP_PKEY_keygen_init(ctx) > 0);
  bail(EVP_PKEY_CTX_set_ec_paramgen_curve_nid(ctx, nid));
  EVP_PKEY *pkey = NULL;
  bail(EVP_PKEY_keygen(ctx, &pkey) > 0);

This works on all platforms that I tested, but on Travis CI the final
call fails with error:

  In EVP_PKEY_CTX_ctrl: invalid operation

I am using a standard Ubuntu 14.04 with libssl-dev. What might be the
problem here?