Thank you all so much for the detailed information on unlocking a Treo 650. I unlocked a phone given to me by a friend and here are the simple steps it took for anyone interested in the future:
  1. Call AT&T customer care at 800-331-0500
  2. Enter the phone number of the phone you are trying to get unlocked
  3. The cust care rep will ask for the first and last name and last 4 of the SSN of the person who had the phone last
  4. With this information he/she should be able to provide an unlock code

Now you can follow these steps to unlock:
  1. Turn phone off
  2. Insert SIM card you wish to use with the phone
  3. Turn phone on
  4. Ensure phone is in Wireless Mode by using the Menu and going to the Settings option
  5. Press the green call button
  6. Enter *#*#<unlock code>#
  7. Press the green call button

That should be it! Thanks!