After further research, while PUSH and PULL sockets work with ROUTER, they are not valid socket combinations as per the ZeroMq spec.
A DEALER socket on the client side is a better approach. DEALER supports bidirectional message transfer, basically doing the job of PUSH and PULL but with a single socket.
I started a thread on Github discussing the issue, it includes some sample code for agent-based pattern using DEALER.