I'm having the exact, same problem as windzilla with exactly the same message and dpkg -r doesn't work returning the same error code.
"error exit status 139 Errors were encountered while processing:"
I don't have fennec or Canola installed so there either must be some other app that is using xulrunner or xulrunner may be be segmented. Note that the installed xulrunner says that it is "broken but able to update."
Any help would be appreciated.