I'd definitely be interested. There was a service that allowed you to do this for a bit, Bitcoin Wireless. There scope was pretty wide as they allowed you to pay for cell phone service anywhere in the world. If I remember correctly they had some issues during their beta and shut the service down (it was run by bitinstant).
If there were a service that allowed me to pay for my cell phone with Bitcoin I would use it. My 'contract' is just about up and I'd much rather switch to prepaid with Bitcoin than continue with a contract on a carrier.
Would you be offering this in your specific store or be offering this via an online site?