Tom Steinberg posted a good idea in the comments section of the "Why Social Software" entry:

Does anyone have access to Lexis? If so, we could run a straight and simple media trawl for the phrase "social software" over the last decade.

Nexis (Lexis is just the law db) shows nothing prior to 1991, However, particularly in those days, print media was a trailing indicator. Further complicating things is the use of the phrase to refer to lots of things, as both words are common: its been used for software that interacts with other software, and for software for making wedding invitations and party invites.

Usenet, on the other hand, was a leading indicator, and the earliest usenet reference I can find is to a 1987 paper by the Foresight Institute, written by Eric Drexler, talking about the social possibilities of a hypertext publishing system"

A hypertext publishing medium will have abilities beyond supporting improved critical discussion. Since it is computer-based, it can naturally support software for collaborative development of modeling games and simulations [29] (and enable effective criticism of published model structures and parameters). Social software could facilitate group commitment and action: individuals could take unpublicized positions of the form I will publicly commit to X if Y other people do so at the same time. Once Y people take a compatible position, everyone's commitment (to making a statement, forming a group, making a contribution, etc.) could be automatically published. The possibilities for hypertext-based social software seem broad.

This is the earliest appearance of the phrase I can find in its Coatesian sense (which I am compressing to "software that augments or extends group interactions.")