CNAME Record with any other Resource Record in BIND

I had pretty much exactly the same issue on an Ubuntu server and it turned out to be two problems:

(1) apparmor

I don't know if the same is true for Debian, but on Ubuntu bind9 is run with apparmor enabled. This means it is only allowed to write to certain places. The places are listed in /etc/apparmor.d/usr.sbin.named, and it is generally advisable to stay within these directories. You can install the apparmor-utils package and (temporarily) disable apparmor for bind to see if this causes your issue:

sudo aa-status

should show /usr/sbin/named in the list of enforced profiles. Then run

sudo aa-complain /usr/sbin/named

to put it into complain mode.

(2) zone file

Almost no manual/tutorial mentions this, but bind9 expects an (pre-)existing zone file to work properly. The end of file error could be caused by the fact that zone file doesn't exist yet (/etc/bind/primary/example.com and /etc/bind/primary/sub.example.com in your example). You can simply create one like this:

echo "; DO NOT EDIT MANUALLY - use the \"nsupdate\" utility to prevent data loss
;
\$ORIGIN example.com.
\$TTL 86400  ; 1 day
@    IN SOA  ns1.example.com. hostmaster.example.com. (
       2009074711 ; serial
       7200       ; refresh (2 hours)
       300        ; retry (5 minutes)
       604800     ; expire (1 week)
       60         ; minimum (1 minute)
       )
   IN  NS  ns1.example.com.
ns1    IN  A  <IP of your bind server>" | sudo -u bind tee /etc/bind/primary/example.com

From your description I can't tell you exactly what is the problem but I can help you rule out several things.

The cache size settings and cache ttl settings are for cached recursive query data and (as you already suspected) don't apply to authoritative data. Similarly rndc flush is inapplicable here.

Suggested troubleshooting method:

1. Verify that the notify messages are being sent by the master as expected. Check the logs and/or sniff traffic between the master and slave.
2. Verify from the logs that the notify message is being received by the slave.
3. If you cannot see the slave receiving the notify, troubleshoot as a notify issue, i.e. double-check your notify options in named.conf on the master, making sure they are defined as you expect, are not overridden later, and are scoped appropriately. I recommend using "notify explicit;" with "also-notify {slave-server;};"
4. If the slave is seeing the notify, your issue is figuring out why the zone file is not being updated as you expect. What should happen is after the notify is received, the slave should make an SOA query, compare to its current SOA, and do an AXFR (or IXFR if you have enabled it) to get the updated zone copy (assuming the SOA on the master is higher.) You should be able to observe all of this happening with a sniffer and you should also be seeing evidence of it in the logs on both servers.
5. If operations do not occur as you expect, start by manually comparing the SOA serial numbers on the two servers (dig @server $zonename SOA) to make sure you didn't accidentally give the slave a higher-than-expected serial number some time in the past which is now higher than the master's serial number.

If that doesn't work, consider posting more information, including named.conf sections from both the master and slave and logs from both servers of what is occurring after you load a freshly edited zone on the master.