Finally figured it out.
When deleting the rows from the datatable i was using:
This completly removes it from the datatable so when the SqlCommandBuilder came around to deleting it from the database it never knew it existed in the first place.
For it to work you need to flag the row as deleted but not actually delete it.
By doing this it all worked.