Very odd behavior - gateway unreachable from client until ping FROM gateway is run to client

A quick history; client has a network with about 100-150 devices at any given time, had an old HP Procurve stack that had a failure in PoE and a fan failure so we had to replace it. All new UBNT switches, connectivity in the stack is with 1gb fiber sfp and local communication seems to be no problem.

Since the replacement, we have users (both wired and wireless) that will get an IP from DHCP with no problem, can communicate with the servers and other network resources but have no internet access. Some of them can ping the gateway (Watchguard firewall) but still have no access and others can't ping it at all. My own laptop had this behavior when I got here this morning tracert times out, ping would go through but I couldn't get to the internet and I couldn't access the management interface on the gateway (both web and System Manager). Logging into a server that has working access let me connect to the firewall without issue. When I ping from the firewall diagnostic tool to MY local IP, the first packet fails, the subsequent ones go through and all of a sudden I can get to the internet and manage the firewall.

Now, this is my first day dealing with this as I just came back from holidays, but my boss has been looking into this essentially since I left. My thoughts are that somehow there is an issue with ARP finding the gateway via the switches until the gateway establishes a path TO the client at which point the stack knows how to get back to the gateway. Am I losing my mind here or does anyone else have some insight as to what might be the issue?