Scottrade offers put writing. If you applied and weren't approved, then you might start with calling customer service and asking for the approval. If they still won't then other options trading services or just regular brokerage accounts might work. Consider:
Fidelity
TD Ameritrade
Interactive Brokers
Options Express
... just to name a few
The risk of switching to any other broker is all the same: have you researched broker solvency? Do they offer a similar or lower fee structure for your trading profile? Are their tools and research as good? Are they compatible with your machine (many advanced trading platforms won't work on Mac, like some of Fidelity's and TD Ameritrade's)? Make sure to do your homework and pick a broker who will keep your money safe, provide you with affordable commissions, and offer good execution of trades you are likely to do.
As the previous comment noted, Options First is the same company as Scottrade. I'd like to say that switching to them changes little -- but you'd be surprised how different the decisions like credit choices, fees, etc. are from division to division of big companies. The advantage of staying with them of course is single point of service, espeically if you make use of the local Scottrade offices.