Very odd i think.
But maybe you have some problem with software-firewall (maybe Windows Firewall) on the clients? Maybe different categorization of company-network, public-network and private-network depending on if you are connected by wire or wireless? Normaly in that i case i would expect that deployment will never be successfull or will always work, but you said that when you try several times it may work.
are Wifi and cable-network split by a router / Firewall or is everythin in the same subnet?
Cable network is connected to Linksys AP, and i guess subnet is same.
Okay, how long did you wait after switching to wifi before you tried to deploy your agent?
What are your settings for agent contact method? (menu -> configuration -> serversettings -> agent contact method)