The test for displaying headings is in a loop that goes through the categories, but does not go through the all/featured/new/specials links. Those are separately output after the categories.

The way to accomplish this will be to copy the heading code to the specials output area. I am away from my home computer now, but when I get back I will look at the files and post here with the necessary code.