I had the same problem, so its way to answer:
1) make sure you set the jobs to backup File-modification time (not the default which is reset archive bit)
2) you must use the same slection list for FULL and INC (this makes sense if you think about it)
3) if you read the manual, it says INC will only function **if** the FULL was successful (exclude files if needed)
4) the media-set must be the same
5) I also noticed that when I tried to (manually) modify the existing FULL job and re-use it as incremental it will always do a FULL; the solution is to make a COPY of the FULL job and rename it to INC (and also set INC options)- the gist is make sure you have both FULL and INC jobs active.
Once I did this, it works ever since.
PS: And this is not mentioned in any manual; you can create a job for an external disk (/Volumes/DiskA) and the connect it to another server; just update the selection list (make sure to delete the original server) and it will still perform a correct INC backup when attached to another server. I even connected the disk locally to my Windows server (using MacDrive7) and the INC still worked fine.