I notice below that you say that “I've ensured that I call AcceptChanges beforehand”. Don’t do that! AcceptChanges will change the EntityState of the Entity to “Unchanged”. Then when you call “SaveChanges”, it will not save the Entity to the datababase because it’s EntityState is Unchanged. SaveChanges will only save an Entity if its state is Added, Modified, or Deleted.
The other advice that I have is to look at a successful example. There is a Silverlight example in the Learning Resources under Business Object Persistence under Adding and Deleting.