sh404sef puts 404 header when included by some reason. That's why AJAX listing displays "There was a problem with the request.", because its returned status is 404 not found, which sh404sef has set up.
I don't think I should put a "fix" for something that's done incorrectly in another component. However, even though it's not a real solution, you can skip the error by editing modules/mod_ajaxlisting.js file.
Find this line:
if (lst_http_request.status == 200) {
replace it with this:
if (lst_http_request.status == 200 || lst_http_request.status == 404) {
