I did about the same as PAT suggests, but then changed my phone service to VOIP, since there are no CLECs here. I had Packet 8 for well over a year, but recently changed to Earthlink. Both are very good services. Packet 8 consumes less bandwidth, but the voice quality is a bit lower. About the only impairment still noticeable with Earthlink is delay, which can cause a few collisions in conversations until you get used to it. They both offer flat rate service to the US and Canada for less than telco local service.
Unless they are now insisting that nobody use their last name as a user ID, it might help to suggest that you think they are committing some sort of ethnic discrimination. If you get ahold of a supervisor, you might wonder whether the PUC or newspaper might agree. I wouldn't actually threaten, however.
You are right that 's**en' isn't profane, or obscene. If that is the reason they are objecting to your ID, they must have infuriated a huge number of users who have recognizable letter strings in their names.