Open the database with a full access password
Open manage | security and edit the privilege set for your limited access users.
Check the options selected in the "availabel menu commands" drop down in the lower right corner. My best guess is that you will need to select a less restrictive option in this drop down so that "new record" is a permitted menu option for users with that privilege set.
Thanks for the help!