Adding a "Fax Number" when adding a new contact in my iPhone 5, ios6
On your contact, click on the label type : 



And it will give you access to the label types. 

These are iOS 7 screens, but it's the same on older versions !