Что ваш соответствующий DomainService имеет на сервере?
Имеет ли он метод DeleteAlbum, который присоединяет альбом к DataContext Linq-to-SQL и затем вызывает DeleteOnSubmit?
Несколько вещей, чтобы попробовать -
Переопределите SubmitChanges на сервере и добавьте try / catch, чтобы увидеть, не попадаете ли вы в какое-то исключение.
В качестве альтернативы на клиенте передайте обратный вызов в SubmitChanges (т. Е. Используйте другую перегрузку) и посмотрите, имеет ли свойство SubmitOperation, переданное в обратный вызов, свое свойство HasError, равное true, и значение Error.
Надеюсь, это поможет сузить проблему ...