Thank you for posting the photo, Adrian.
This is an interesting cichlid!
I believe, however, that it is no Astatoreochromis species. Your fish shows none of the typical color traits for that genus (i.e. fin coloration, arrangement and number of anal ocelli etc.), has a subtruncate rather than rounded caudal fin and fewer dorsal fin spines (I count XIII on the photo, vs. XVI-XX in Astatoreochromis). In these features it agrees rather with Haplochromis (a dorsal fin spine count as low as XIII would even be unusual [though not unique] for them; normally, there are XIV-XVI), but it seems to be clearly distinct from the more slender and differently coloured (though insufficiently known) Haplochromis stappersi. It seems to be also distinct from other Haplochromis species (several of them undescribed) known to occur in the Malagarazi and Lake Rukwa drainages (the ichthyofauna of the latter shows certain similarities to that of the Upper Kalambo, although no cichlids were found in the possible area of faunal exchange; Seegers 1996). Finally, an identity or even a close realtionship to Astatotilapia burtoni, which is known to occur in the Kalambo below the falls, can be excluded.
Therefore, at least if the figured fish is representative for its species (have you more photos?), it seems that you have found a new species.
With respect to Astatoreochromis, the figure of A. straeleni is inaccurately redrawn from Poll's original figure, especially with regard to the dorsal fin spines. The species A. straeleni and A. vanderhorsti are insufficiently delimitated against each other and were synonymized by DeVos & al. (2001). This action has been largely overlooked so far, probably because the paper contains no descriptions of new species.
I can supply you with the original descriptions off all species and several other relevant works on Astatoreochromis (most of them I have on paper, however, so it will take a little time to scan them). Please let me know your e-mail adress.