Hatte ein ähnliches Problem im Zusammenhang mit IPv6.
Das USG hat den Clients den Netzwerk-Präfix von allen VLANs angeboten. Alle Clients im Netz kamen damit zurecht, ausser Android.
Falls bei Dir IPv6 aktiv ist, schau mal, ob Deine Clients mehrere Global Link Adressen haben. Falls ja, schau mal, ob die ersten 64bit gleich sind. Falls nicht, dürfte das Dein Problem sein.