Date format in general settings won't change

the date format in general settings won’t change anything if your theme isn’t set to accept that.

A lot of themes hard code the date format. I’m guilty of it myself. You can change it directly in the theme by either hardcoding in there where you see the_time (or the_date, but it should be the_time even for date format)
http://codex.wordpress.org/Template_Tags/the_time
http://codex.wordpress.org/Formatting_Date_and_Time

using this the_time( get_option( 'date_format' ) ) would allow the date to be formatted following the settings in general