Maybe there's a bug in the plugin. I haven't tested this, but you could try editing nagios_nsca.rb and changing line 104 to this:
message = "#{nagios_host}:#{nagios_service}:#{status.to_s}:#{msg}"
I saw another similar report that was never resolved. Let me know if that fixes it, and we can dig deeper in the week.