Hi there. Unfortunately, there is not much you can do for a blacklisted phone. It usually means that the phone was reported lost or stolen, or that somewhere along the line someone forgot to pay the bill. The carrier blacklist is not meant to be circumvented. Also, I believe AT&T and T-Mobile share their databases for blacklisted phones, so both networks will not work. Unless you get the previous owner to go to the store with you and prove that it was his phone (so he can get it off the blacklist), there is not much you can do.
Is the Nexus 5 the international version? If so, I read that this might work. Since the phone has GSM/CDMA bands, it could work with Sprint or Verizon since they are CDMA carriers. T-Mobile and AT&T are GSM carriers.
I read it here.
Unlock a Bad IMEI Phone that's Blacklisted, Blocked or Stolen
-Wizzrah, Android Central Ambassador | Sent from my AT&T HTC One X running CodefireX 4.4.2