O problema aqui é como você está representando as datas, elas precisam ser passadas como
Date tipos e em formato de época. Tente isso em vez disso:mongoexport --db store --collection user_data --query '{"order.created_order":{$gt:new Date(1360040400000),$lt:new Date(1360990800000)}, "order.status" : "paid"}' --out ordersfeb6.json
Se você deseja converter ISODate para epoch, basta chamar date no shell, algo assim:
> new Date(2013,01,16)*1
1360990800000
Então para verificar:
> new Date(1360990800000)
ISODate("2013-02-16T05:00:00Z")
Atualização: Conforme observado nos comentários do imcaptor, o mês é baseado em zero (0 =janeiro, 11 =dezembro) na
Date construtor, não é algo que a maioria espera e fácil de esquecer. Passei em 01 no exemplo acima e obtive uma data de fevereiro, como você pode ver no ISODate da verificação. 
