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:
- 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.
- change the validation rules in cutomer_eav_attribute table for the attribute id you are changing (get it from the eav_attribute table)