Welcome to Android Central! Which phone? Are you adding the contact to your Google account or to the Phone account? Is the phone connected to the web, and are you able to access your Google account? Is Auto-sync on?
Try going to Settings>Apps>All, select Contacts, and Clear Cache, then Force Stop. Now open it again and try adding the contact.