Hi Justin,
Thank you very much for the proper details, it helped me a lot.
Yes, the plugin is WPML compatible, but for some reason the requested URLs were returned incorrectly. I am not sure why, but I managed to find a solution. I have placed a small custom code snippet to the functions.php file in your theme directory via FTP. I will look up the WPML support forums to see if I find anything similar, maybe there is a different solution as well.
The result URLs should be okay now.
For future reference, this is the custom code used: