Ishani,
If you view the "Functional Access" tab for the Role what is the Access level for "Contact"? If they cannot create contacts today it's likely "View", you should be able to change to "Modify".
You may also need to validate their data partitions to confirm nothing would prevent them from editing contacts.