db_owner Member Can't Delete on Tables
Unless the users is mapped to the sysadmin fixed server role (where they will connect to the database as the user dbo) then they can be limited by security on the database.  (i.e. A member of db_owner will receive a security check where dbo will not.)

A quick test to see if it is a permissions issue is to temporarily grant a user sysadmin role and then see if they can delete data....  if not then I'd start looking for constraints on tables. 

If they can then run the following against the database (you may get more you may need to add DELETE to your where clause):

select * from sys.database_permissions 
where state_desc = 'DENY'


If permissions are set it will give you something like:

class class_desc                                                   major_id    minor_id    grantee_principal_id grantor_principal_id type permission_name                                                                                                                  state state_desc
----- ------------------------------------------------------------ ----------- ----------- -------------------- -------------------- ---- -------------------------------------------------------------------------------------------------------------------------------- ----- ------------------------------------------------------------
0     DATABASE                                                     0           0           10                   1                    DL   DELETE                                                                                                                           D     DENY
1     OBJECT_OR_COLUMN                                             1501607433  0           10                   1                    DL   DELETE                                                                                                                           D     DENY

(2 row(s) affected)


If deny delete is set at the DATABASE level then well then there is your problem.  Adjust permissions so required users are not actually DENYed access.