I'm seeing a 500 (internal server error) not a 404. Do you have access to the server error logs (what do they list)? The server error logs will indicate the cause of the internal server error (unless the host has disabled logging errors).
Most common causes will be:
- Wrong .htaccess file was modified / replaced
- Server does not have mod_rewrite enabled
- Server does not allow mod_rewrite directives in .htaccess files (overly paranoid security)
- Server has disabled other items (such as follow symbolic links) causing mod_rewrite to fail
- Server is using some sort of internal proxy or REWRITE to access the web root (cheap shared hosting plans often do this often for "secondary" domains)
For the first "guess"... Was the original .htaccess file in the SAME folder as the Zen Cart installation? For example "/public_html/.htaccess"? Or was the original / modified .htaccess file in a parent folder (outside the public web root)?
For the rest may want to ask your hosting provider to investigate the cause. The middle three you cannot fix (only a server administrator can). The last one is something one can create a "workaround" specific to the hosting environment to address... But one would know more details about the server configuration.
P.S. The lines from your original .htaccess file look suspiciously close to the .htaccess file used by cPanel w/ "optimize server" enabled (note this file is usually located outside the web root on server's w/ cPanel - not inside the folder where Zen Cart is installed). As per the Ultimate URLs installation instructions the supplied .htaccess file goes in the same folder where Zen Cart is installed (or is merged with any existing .htaccess file in the same folder where Zen Cart is installed).