Mobile electronic commerce (m-commerce) is an emerging manifestation of internet electronic commerce that bridges the domains of Internet, mobile computing and wireless telecommunications in order to provide an array of sophisticated services (m-services) to mobile users. In such an open market place, the flexible exchange of m-services will necessarily be through some form of negotiation. To this end, this paper investigates the issues associated with such negotiation in facilitating agent mediated mobile commerce (many of which also apply to the wider electronic commerce domain). Specifically, we discuss the protocol and strategies for evaluating and generating sets of issues when negotiating for a service in a future generation mobile telecommunication environment.