Why Do Replication Deletes Require sysadmin Access

So are you telling me that every user of my database has to have sysadmin access if they are going to be doing deletes?

No, as per BOL's documentation on sp_trace_generateevent:

User must have ALTER TRACE permission.

This is now a known bug (present only in SQL 2012), that Microsoft is currently addressing. Workaround is to give user ALTER TRACE permission until is resolved.

You can track status on Connect.