Maybe I missed something but everything is functioning as expected in the live v1.3.9H site for these categories.
Same DB upgraded into the sandbox v1.5.1 site, appears to be functioning randomly different.

In most cases, it is the Default price that is being displayed as the Lowest, Starting At price instead of the actual lowest priced attribute.

I'm pretty sure that the attribute settings are correct, but below is a representative screen print.

Attachment 14212

I just realized that I have other categories, priced by attributes, that are not displaying "Starting at" text in V1.5.1. Only the base price is shown regardless of attribute adders. But those categories do not show the "Starting At" text in v1.3.9H either.