@athei We thought it's an UI issue at first (polkadot-js/apps#5156, paritytech/canvas-ui#95), but now it seems like a contracts pallet bug.
The estimated "max gas value" which the UI's pre-fill for contract calls is for some calls significantly lower than the required gas. So the pre-filling is actually incorrect and the call cannot be executed with the default settings (breaking e.g. our tutorials, which should work with default settings).
How to reproduce
We've found that at least the ink! examples delegator and contract-terminate are affected. contract-terminate is the easiest to reproduce the bug with. I've attached the contract which can be used for deployment here: contract_terminate.contract.zip.
The contract has only one method terminate_me, the polkadot-js UI suggests a default Max Gas Allowed of 1417, but the contract then fails with system.ExtrinsicFailed: contracts.OutOfGas.
It works if the max gas is set manually to 2500.
You can e.g. use the latest canvas-node, it has been adjusted to the Substrate HEAD just this week. canvas-ui is also affected by this.

For the simple contracts (flipper, etc.) the estimation seems to work fine. Those two affected contracts do either cross-contract calls or call seal_terminate.