You could simultaneously write into a second "index" table (in quotes because unlike an RDBMS, there are no automatic declarative indexes that HBase maintains, you have to do it yourself). That table could be based on the modification date in the row key, and contain just enough info to find the record in the main table (for example, it could have the modification date in the rowkey and then the creation date in a column value). Your operation is then a linear scan in this "index" table to find the most recently modified records, and then N GET operations into the main table, one for each record you want to display.
Another design entirely is that you could store one row in HBase per user, with two column families: one for the user's messages (with each column being one message, stored in a way similar to what you describe above except that instead of a row for each discussion, there's a column for each discussion); and then, in another column family, you could store the user's "inbox", which is just a cache of the top N messages ordered by modified date, used to show the inbox. The advantage to doing these as columns instead of rows is that in this scenario, the entirety of the row is transactionally protected per user, so you can do more complex operations like check & set, and you can guarantee that the inbox view is always consistent with the latest messages.
