SQL Server 2008R2 - Stored Procedure with 2 updates causing deadlocks
Using SentryOne Plan Explorer I was able to make a little more sense of the deadlock graph (click to embiggen):


  


The victim also called the stored procedure GetIsAccountLicenseConnectionValid, and I suspect this procedure has some touch against one or both tables affected by the updates in the question. It is certainly feasible that locks taken by that stored procedure could interfere with locks affecting another transaction that hasn't called that stored procedure yet.