Why aren’t certain devices getting an ip address over the wifi

Here is how our network is setup:
We have one Sonicwall NSA 3500 that feeds internet to the entire campus.
Connected to the Sonicwall is a Dell PowerConnect 5548.
Connected to that are the 4 main UAP's (Ubiquiti UniFi access points) for the main building.
The controller (software) is connected to the Dell through several unmanaged switches.
Other buildings are connected directly to the Sonicwall through 2 Rocket M5's and a NanoBridge.

DHCP is handled by the Sonicwall.
There are 2 SSID's Staff and Public

Public is by itself on vlan 205 with 192.168.205.0/24 and a 60 min lease.
Staff is not on a vlan and that interface on Sonicwall is shared with computers.
The network is 192.168.12.0/24 with a 1440 min lease.

Sonicwall handles all routing with the default settings
Also Sonicwall only allows traffic from 205 to go to the WAN, everything else is blocked.

We have had this setup for a couple weeks now, and we have had the Sonicwall and the UAP's for several months without issue. For whatever reason, starting the day before yesterday, certain devices refuse to get an ip address when they connect to either of the wireless networks on any of the UAP's. They instead get a link local address (Which is reported on the controller as their address.)

Each device seems to act consistently, and does not seem tied to brand (Some iPhones have difficulty, some don't etc.):
Some won't get on at all.
Some will get on if you switch networks several times.
Some will get on but occasionally get kicked off then get right back on.
Some don't appear to have any issues. (That I have heard about anyway. It is possible all devices are having some kind of issues that just aren't getting noticed/reported.)

We have tried rebooting all equipment, and unplugging everything on the Dell switch except one of the UAP's and the issues continued. Any thoughts?