Distinct on a non-sort column

I am trying to write a query that selects recent submissions (sorted by
submission_date) but only selects the most recent one for each user_id.

example query: /select distinct on (user_id) * from stories order by
date_submitted desc limit 10;/

However postgres will not allow me to filter out duplicate rows with
distinct unless I sort on that column, which would product useless
results for me. Group by seems to have similiar problems, plus the
additional problem of wanting aggregate functions to be used.

I even tried sorting in a subquery, but it still comes out sorted by
user_id: /select distinct on (user_id) * from stories where sid in
(select sid from stories order by date_submitted desc limit 10);/

How can I work around this limitation to get the results sorted the way
I want, then have the duplicates removed? I can't be the only one
running into this limitation, there must be some workaround.