Hi,
JBattin:
I have added the Ceon rewrite statements to the end of that .htaccess but they don't work (I get a 404).
Stop wordpress overriding the Ceon rewrite rule by adding an exclusion condition to its rule (for the shop directory/URI parts), or, since you are running the store at least one level down, put the Ceon rewrite rule before the wordpress one, whatever it is (never used WP myself, it's a [poor man's] competitor to Ceon's aarck/aawe system ;) ), and add an exclusion for wordpress' URIs.
JBattin:
If I remove the blog rewrite stuff then the categories will work (the product pages don't, the product pages work, but the links are not canonical).
That's a mistake by you then. You've missed something when installing Ceon URI Mapping or your template is missing the necessary Zen Cart code to use it - the $canonicalLink stuff (on 1.3.8 this is easily missed as html_header.php also needs modified in that ancient version).
Make sure you have the Ceon URI Mapping modified version of init_canonical.php in the includes/init_includes/overrides directory.
Hopefully the above is enough to get you sorted.
If not then you should install the software from scratch again to fix whatever you missed.
All the best..
Conor
ceon