Welcome to Android Central! I'm assuming that the contacts that you lost are from the "Phone Account," as opposed to contacts that are from your Google account. Phone Account contacts are only stored locally, typically on the phone itself and on the SIM card--they don't sync with Google, but you can sync them with other programs like Outlook using other 3rd party software (e.g., Kies, HTC Sync, Verizon's Backup Assistant, etc.). This is why I always recommend against entering contacts into the Phone Account--they're not easily synced or backed up.
First off, make sure that the People or Contacts app is set to show all contacts, and not just Google or Facebook contacts. Look at the settings for People/Contacts, and see if there is a setting for which accounts to display. Make sure the Phone Account is selected to display.
If that doesn't work, then did you have to change SIM cards when you switched from AT&T to T-mobile? If so, then maybe that's how the local contacts were lost, since they're usually stored on the SIM. What's odd is that they should also have been stored locally.