Deadlock on Insert/Update
Updating any of the NC index keys is an update that has potential to deadlock. This is the typical read-write deadlock due to different access paths. Even if you update different keys, that doesn't eliminate conflicts because the locks are on key hashes, see %%lockres%% collision probability magic marker: 16,777,215. However, you describe the problem as appearing 'immediately' which strongly suggest that some other factors are at play, and we can only speculate about in lack of actual information.

Of course it would be much more useful to capture the deadlock graph and post it here. Discussing on a mere description of the deadlock has only limited value, as your description may or may not be factual, your understanding may or may not be correct and our interpretation may or may not be accurate.