I'm sure you have this figured out by now but it might help someone else.

I am using Magento CE 1.9.2. In addition to what you have already done, try this:
1) comment/delete required class in `*app/design/frontend/PACKAGE/THEME/template/persistent/checkout/onepage/billing.phtml*`. You might also have to do the shipping.phtml as well depending on your needs.

2) change the validation rules in *cutomer_eav_attribute* table for the attribute id you are changing (get it from the *eav_attribute* table)