lucy24 - 12:25 pm on Feb 20, 2013 (gmt 0)

Uh... You've got example.com and store.example.com living in entirely different physical locations? With DNS set up to point requests for store.example.com to the new place and plain example.com to the old place? I'm getting a headache just thinking about it.

What are the Conditions for?
RewriteCond %{HTTP_HOST} ^example\.com [OR]
RewriteCond %{HTTP_HOST} ^www\.example\.com
If this is happening in your old site's htaccess then the host can't be anything but your basic domain, so you don't even need to consider it. A simple, conditionless

RewriteRule ^store/(.*) http://store.example.com/$1 [R=301,L]

should do it.

Other than example.com/store/blahblah which is now going to store.example.com/blahblah, what's left at example.com ?