Dideved - 6:07 pm on May 8, 2013 (gmt 0)
Your first two redirects seem perfectly fine.
Can we assume that a category will only ever be exactly one path segment? If so, then this seems to do the trick.
RedirectMatch ^(/[^/]+)$ http://new.com$1/
This will need to go between your two current redirects.