call it LocalizedException and provide messageKey and messageParams methods. Use the messageKey to lookup a format string in a resource bundle containing a message format string - then unify that with the messageParams with java.text.MessageFormat.

You can have the exception class do the lookup of the bundle, or leave it to client code. I'd be inclined to put it in the exception itself - implementing something like toString(locale).