In this paper we present the results of a genuinely multi-dimensional relaxed upwind scheme for an arbitrary system of conservation laws in two space dimensions. A new discrete velocity Boltzmann equation is proposed, which is an improvement over the previously introduced models in terms of the isotropic coverage of the multi-dimensional domain by the foot of the characteristic. A finite volume method has been developed in which the fluxes at the cell interfaces are evaluated in a genuinely multi-dimensional way, in contrast to the traditional dimension by dimension treatment. Second order accuracy of the scheme is achieved by using standard MUSCL type reconstructions and TVD Runge-Kutta time discretizations. The results of several numerical experiments on the compressible Euler equations are presented which confirm the robustness and correct multi-dimensional behaviour of the new scheme.