Once you set up synchronisation to an Exchange server (not sure about other enterprise mail/messaging platforms), your default contact group store is the Exchange contacts list. The contacts synched with Exchange cannot accept custom labels created via the iPhone, so you no longer have the "Create custom label" option.
You can still add custom labels to the contacts that are stored on the iPhone though. However, to store a contact on the iPhone when the phone is synched to Exchange, you have to go into the "Contacts" list, press the "Groups" button in the top left (this will give you options for "All Contacts", "All from my PC", and two Exchange items: "Contacts" and "Exchange Global Address List".
Press the "All from my PC" option, and it will show you any contacts that are stored on the phone instead of in the Exchange server. These contacts can take a custom label. You can add contacts to this list as normal, with the "+" button in the top right.
To add a custom label, click on a Contact, click the "Edit" button in the top right, click on the label that you want to change (the label, NOT the number, email or address), scroll to the bottom of the label list and choose the "Add custom label" option.
One option for adding a custom label may be to add it to a contact through Outlook, but I cannot test this as I only have the web-access version of Outlook while I am out of the office (my default state), and I am 99% sure that this would not work, but it is the only option I can come up with for adding custom labels to Exchange contacts at the moment.