Go to the Record Type settings for the standard and custom objects. Click on the record type and you'll see the "Picklists Available for Editing" section. From there you should be able to add the new picklist values.
The picklist values at the field level are like a master list. Using record types you can allow only a subset of the list to show up.