Several errors or let me say mistakes are in the example above.
<sid>sid</sid>
is wrong. you first need to do a login call to get a real SID and the place this session id in any further SOAP call as the <sid> value
<creatorHandle>A5F1C9C1011C764FBB982EFAB76ADCB0</creatorHandle>
you need to specify a so called cnt persistent id as you did in all other so called srel attributes values
so something like this might work:
<creatorHandle>cnt:A5F1C9C1011C764FBB982EFAB76ADCB0</creatorHandle>
<string>tenant</string>
<string>31635402584F964A95C8D7277C070306</string>
remove the tenant stuff. the tenant is set automatically by the system.
<string>category</string>
<string>pcat_cr:1121023953</string>
I wouldn't use "pcat_cr", go for the following:
<string>category</string>
<string>pcat:1121023953</string>
<string>priority</string>
<string>pri:2</string>
pri:2 is not a valid persistent_id for a priority , the following might work
<string>priority</string>
<string>pri:503</string>
as Raghu suggested add
<template></template>
right in between
</propertyValues>
<attributes>
it is part of the soap schema and must be provided even with a null value
In general make sure that all referenced persistent_id's exist.
With these changes and of course persistent id's of my own system and after removing your custom attribute, the soap request was working on my test box
Hope this helps
Best regards
.........Michael