Further digging reveals that there is sexual innuendo at work:

to call a spade a spade - to use simple language - the expression is not an ethnic slur, which instead is derived from 'black as the ace of spades', first appearing only in 1928. The expression 'to call a spade a spade' is much older, dating back to at least 423BC, when it appeared in Aristophanes' play The Clouds (he also wrote the play The Birds, in 414BC, which provided the source of the 'Cloud Cuckoo Land' expression).

'To call a spade a spade' can be traced back to the original Greek expression 'ta syka syka, ten skaphen de skaphen onomasein' - 'to call a fig a fig, a trough a trough' - which was a sexual allusion, in keeping with the original Greek meaning which was 'to use crude language'. At some stage between the 14th and 16th centuries the Greek word for trough 'skaphe:' was mis-translated within the expression into the Latin for spade - 'ligo' - (almost certainly because Greek for a 'digging tool' was 'skapheion' - the words 'skaphe:' and 'skapheion' have common roots, which is understandable since both are hollowed-out concave shapes).

This crucial error was believed to have been committed by Desiderius Erasmus (Dutch humanist, 1466-1536), when translating work by Plutarch. The translation into the English 'spade' is believed to have happened in 1542 by Nicolas Udall when he translated Erasmus's Latin version of the expression. While the origin of the expression is not racial or 'non-politically-correct', the current usage, by association with the perceived meaning of 'spade', most certainly is potentially racially sensitive and potentially non-PC, just as other similarly non-politically correct expressions have come to be so, eg 'nitty-gritty', irrespective of their actual origins. (Developed from Mark Israel's notes on this subject.)