For both standard and custom objects, go to the Record Type settings. The "Picklists Available for Editing" section appears when you click on the record type. You should be able to add the new picklist values from there.
At the field level, the picklist values are similar to a master list. Only a subset of the list will appear if you use record types.