Is it possible that your Verizon iPhone has a newer version of iOS than did your AT&T iPhone? It could be that Apple accidentally borked some of the necessary components to interface with your car.
As for Airplay... I don't have iOS devices anymore but that should not be network-dependent as it operates over wi-fi. Of course if your iPhone was connected only to 3G data and not to your home wi-fi, it would not find the printer.