Did you find an answer meanwhile? I'm having the exact same problem with my 7941, running SW version SIP41.8-4-3S.
Tried the below dialplan, but no success. In fact the # character is passed on to asterisk, causing the error "Your call can not be completed as dialed".
A 7960 phone in my network works great, using the same dialplan, and without changing anything on the asterisk site.
<TEMPLATE MATCH="*#" Timeout="0" User="Phone" />
<TEMPLATE MATCH="*" Timeout="4" User="Phone" />