Device-to-Device (D2D) communication that enables nearby mobiles to directly communicate one with another is a new paradigm aimed at increasing the capacity of next-generation wireless networks. The coexistence of D2D and cellular communication in the same spectrum poses new challenges for resource allocations and interference management in a large-scale wireless system where each mobile strategically selects its mode of communications. This paper formulates a game-theoretic framework to capture the distributed strategic behavior of a large population of mobiles in selecting their mode of communications. In particular, we investigate the impact of Queue State Information (QSI) of the base station (BS) on the mobile decisions, and we show that the common knowledge of QSI can induce bad quality of service for standard cellular traffic, when the capacity of the base station is below a certain threshold. This paradox will be used to guide the design of optimal learning and scheduling algorithms for the coexisting D2D communication networks.