Which operations (e.g., Create, Delete, Update, Query) have you specified as 'allowed' for Feature Access within the service properties? Also, you should check the requests and responses using Fiddler. What are the results from running Fiddler during the attempt to add the new feature?