Cingular CSRs are notoriously incompetent in some regions. The vast majority of customers in those regions don't even leave the state, much less go int'l! So invariably they'll either just flat out not provision the phone properly or misprovision it. Contrary to what they tell you, int'l dialing capability DOES NOT denote roaming capability. Many confuse the two. So likely you simply didn't have the feature turned on. What you describe is exactly what happens when you don't have int'l roaming authorized/provisioned properly.
As for the network select, that's a combination of the software and the SIM. It's actually driven by the SIM card. Some Cingular SIMs didn't have network select disabled and the option will be there. With any other sim, you'd see the feature if the phone weren't SIM locked. Why you see it when you go abroad is that the SIM is intelligent; if it doesn't see a Mobile Country Code of 310/311 (which are the US codes), it allows network select. ALL US carriers begin with 310/311. Go to canada and you'll have net select, same in Mexico.