Usually when a tenant needs a lease to get utilities turned on, it means the utilities were previously turned off at that address for non-payment and the utility company wants to be sure they aren't turning the service back on for the same occupants. So you have a history of problem tenants, right? You need to vet your prospects better and get your paperwork in the proper order.
Always use a holding fee agreement and take a non-refundable holding fee when you are committing the rental to a tenant for a future date. Never sign a lease until the day you are prepared to hand over the keys. Never sign a lease until the tenant has paid all SD and rent up front in cash and provides proof utilities are in their name (they can use the HFA to get them turned on, if necessary).
At this point, you have a signed lease good through May 28. Tenant could sue you for constructive eviction since you are withholding the key, but they may not win because of the conditional language in the lease related to required tenant actions (utility transfer & payments). You will probably have to go to court to sort this one out. A simplier solution would be to let the tenant know that you will be giving them notice immediately for non-renewal of their 1-month lease, so they will have 2 months in the unit (May and June) total and you will sue them for non-payment under the terms of the lease. OR in the alternative, they can have their money back less the fair rent for the period you have held the unit for them so far, and everyone walks away; you will provide a written release and all parties will sign it.