Formula Columns Not Working: Troubleshooting Common Issues

Formula columns stopped working for any type of the logic, even basic condition like "is not empty" does not produce any result. Need help from support to take a look, maybe some bug in the product.