Correct way in new versions of nginx

Turn out my first answer to this question was correct at certain time, but it turned into another pitfall - to stay up to date please check Taxing rewrite pitfalls

I have been corrected by many SE users, so the credit goes to them, but more importantly, here is the correct code:

server {
       listen         80;
       server_name    my.domain.com;
       return         301 https://$server_name$request_uri;
}

server {
       listen         443 ssl;
       server_name    my.domain.com;
       # add Strict-Transport-Security to prevent man in the middle attacks
       add_header Strict-Transport-Security "max-age=31536000" always; 

       [....]
}

The rewrite directives seem to be correct.

However, from your provided information I can't tell you much about what is wrong.

• Find out where the 404 happens: before or after the redirect.
  Examine the log files or use in-browser development tools (like Firebug) to follow the redirect flow.

• Is that given snippet all you got inside the server block? What about the logic that handles the redirect targets?
  You should post the rest as well.

• Also, look out for other location blocks possibly interfering with the URLs.
  See the nginx docs for the order of matching locations.

Update: Guess I found your mistake:

The location ~* \.(html|htm)$ block matches all your requests usually going to /classifieds/ because regular expression are prefered by the mathing engine by default.
To raise priority of location /classifieds/ you should use the ^~ flag:

location ^~ /classifieds/ {
    # REWRITES HERE
}

Corresponding docs entry:

It is possible to disable regular expression checks after literal string matching by using "^~" prefix. If the most specific match literal location has this prefix: regular expressions aren't checked.

Redirect loop:

It seems like you want to keep the SEO-friendly URIs for outer appearance.
In this case, modify the rewrites to only rewrite internally - without redirecting the browser.

To achieve this behaviour, use the last flag instead of permanent as follows:

rewrite SEO-PATTERN INTERNAL-URI last;

The location match engine will then try to match the rewritten URI.
While redirect and permanent trigger a HTTP redirect (temporary/permanent), last and break will only affect the internal URI value.
It is all described in the docs.