Wow... Never thought this thread would come back to life... but I'm glad it is. My C56 is still alive and well; I use it once in a while.
Props to you on at least attempting to recycle an old phone. It's the right thing to do.
To identify exactly which model it is, just press *#06#, and you'll get the IMEI of the phone. Press INFO and you'll see the info screen. Scroll down to the second last line and you'll see a line like: "Product: C56". This will tell you the exact model number.
As you could probably gather from reading this thread, the innards of the A56 and C56 are the same, and the outer cover and keypads are interchangable. Technically it's possible to make an A56 into a C56, and C56 into an A56, but this is only by firmware modification, and not SIM-dependent. A SIM will have the power to lock out access to certain menus, for example, SIM cards from Rogers or Fido here in Canada do not allow access to the call timer menu, I had to use an old AT&T card to get into that menu. However, SIM cards will not have the power to make a C56 function only as an A56, for example.
I'm not in the US and thus have no idea what exactly happened to the programming of the new AT&T SIMs since the rebranding from Cingular, but here's what I can offer for now: the "AT&T" tag you see when your phone was active was pretty much a "patched" logo sent over the air. With it inactive, the "Cingular" tag simply came from the phone's software. So, we can be pretty sure at this point that the phone is locked to Cingular SIM cards, or what became of them nowadays as the new AT&T network. Thus, it would be safe to say that the receipient would have to be an AT&T customer.
Perhaps you could borrow an active SIM from someone with a newer AT&T SIM card and try the phone out?
Nokia: 5160i, 6160, 8260, 3390, 5190+analog, 8390, 3595 (x2), 6010, 1100b, 6061 (x3), 7250i, 1112b, 1208b, 2760, 3555, C1-01, C3-00
Siemens: A56>C56, M55
SonyEricsson: T28w, Z200, T226, T290a, Z310a, Z520a>Z525, W710i prototype, W300i, T303a
Motorola: MicroTAC Lite, StarTAC 6500, V547, W233