After more than three weeks of searching and appointments, we found a grocery store to accept our bitcoins. It turns out, it was one of the first grocery stores we approached -Lolo's Fresh Food Warehouse in Provo, Utah.
http://www.lolosfoods.com/. It just took considerable time to get it all arranged.