The problem is that I had called the 'wiced_hostname_lookup' function with a timeout value of WICED_NEVER_TIMEOUT. This translates to "-1".
The 'dns_client_hostname_lookup' function (that does all of the work) uses the initial timeout value in a "while" loop for multiple DNS lookup attempts, each time counting down the remaining timeout value until it goes negative.
Therefore, by passing WICED_NEVER_TIMEOUT, the "while" loop was never executing which made the function report the error.
It really is a pity that the documentation is not written with proper descriptions of the functions actions, the valid (or invalid) ranges for the parameters and the meanings of the return values.