Use
ORDER BY videos.posteddate
select distinct top 5
videos.videoid,
videos.videotitle,
videos.videoname,
convert(varchar,videos.posteddate,106) as posteddate,
videos.approvedstatus,
videos.videoimage,
(ISNULL(videos.views,0.0)) as [views],
videos.privacy,
(isnull(videos.rating,0.0)) as rating,
videos.userid,
users.userid,users.username
from
videos
left outer join
users on videos.userid=users.userid
where
videos.approvedstatus='Y' and videos.privacy='P'
order by
videos.posteddate desc
Seu original é o equivalente a
ORDER BY convert(varchar,videos.posteddate,106) DESC
Então você está classificando pela string "dd mon yyyy", não pelo datetime real desejado (yyyy-mm-dd hh etc)
Eu acho que este é o SQL Server 2000:da memória o SQL Server 2005 não aceitará essa ambiguidade