Hello John,
Do you have a DNS server on the clients, are you providing it via DHCP,
You can use PAT on this scenario with no issue at all,
can you share the running configuration of your ASA and the ipconfig /all of one of the clients
I will proceed with the solution afterwards
Julio Carvajal
Senior Network Security and Core Specialist
CCIE #42930, 2xCCNP, JNCIP-SEC