The solution is actually simpler than that. Just shut down any company operations in Utah, refuse to accept any payments from users with Utah addresses and require all of your employees that are located in Utah to relocate. But people in Utah can continue using the service.

It's also quite possible that this law gets thrown out as unconstitutional by the federal courts since it seems similar to the California video game censorship law from Brown v. EMA.