most HotSpots have ZeroConf service available, including most modern Apples'. Your Arduino should work at Starbucks, as well.This may give a test you can try.
I don't want to recommend a new router to you, there is no telling that a new one would be any better. Do you have the option of loading a different firmware on your router, something like DD-WRT or OpenWRT? I use DD-WRT because it's supported by my router manufacturer, and OpenWRT is of course what you're already running on the Yun. Both will give you a lot more configurability than the stock firmware (as well as give you many more ways to do something wrong!) Note that this is a complex scenario, and I won't be able to help if things go wrong.
This is equivalent to fixing the toilet on a house with one bathroom, if you have to do it you want to make sure you have everything you need on hand, and with adding custom firmware to a router my assumption is that I'll break it (at least for a while)!
@jessemonroy650: I never did take the yun out of the house, but installing openwrt fixed the problem (as suggested by @ShapeShifter)... I think in fact it was your instructions on the openwrt forum that showed me how to set up the router to simply be an access point. I mean it was definitely this set of instructions, but I can only speculate that you wrote them because it is possible that the jessemonroy650 on the openwrt site is not the same person...::::SNIP::::