Gas required exceeds allowance (0)

Hello everyone! I’m trying to send a transaction to a GSN-enabled contract I deployed on rinkeby, but unfortunately I keep getting this error:

Error: Rejected relayTransaction call with reason: Returned error: gas required exceeds allowance (0)

The same transaction seems to work if I send it using the same account as the deployer (no gas used, so it’s working fine) of the contracts, but fails with that error when using any other account.
Weird this is that running the same code on a local node it works perfectly fine!
I would appreciate if anyone can give any clue about what this error is about.

UPDATE: Seems like the problem is the web3 estimateGas function. I hardcoded the gas used by the same transaction on localhost and now it works just fine, but this isn’t a solution. How is it possible that the estimateGas fails when the actual transaction has no problems to be executed?

Thanks in advance!