I'd suggest exactly what they did.
1. Log the user's threats if you haven't already.
2. I'd try checking the identd of the user and banning it - if a ban on an IP address doesn't work, I'd suggest using the identd for now, until you can figure out some way to make a stronger channel ban. Also, I wouldn't let them SEE that you're banning the identd as well as their current proxy IP address. Kick-Ban them from the channel, find out what their identd is/was and add it if they keep it consistent. It may take them a little longer to figure that the identd is the reason they can't come back in. I know it sounds rather strange, but I'd try it all the same.
3. Find out what the help channel is on your network by typing /list or /list help
4. Contact an IRC Operator in one of the channels regarding this. I wouldn't ask for them to k-line right away; logs CAN, unfortunately, be faked, so the oper may want more proof if you want the person to be k-lined, to be sure the k-line is placed justly. Be as helpful as you can to the IRC Operators.. perhaps request that they watch the channel or watch the user for a time if you want the person to be k-lined and/or g-lined.
5. Don't worry about the threats much - the likelihood of someone being able to carry out those threats is very small. Concentrate more on getting help from the IRC Operators, as I'm sure they don't want someone like that hanging around on their network.
Hope I helped even a little bit. =)
