I would return 500 as well, with details in the payload indicating what went wrong. This is the description for 504 from RFC 2616:
The server, while acting as a gateway or proxy, did not receive a timely response from the upstream server specified by the URI (e.g. HTTP, FTP, LDAP) or some other auxiliary server (e.g. DNS) it needed to access in attempting to complete the request.
That error description for 504 indicates that the server is acting as a gateway or proxy, which your service is definitely not doing.