The primary difference between the two is the question of "how many"?
In the role hierarchy, you are allowed one role as a user. So if I am in a sales hierarchy where it is only regional (East, Central, West, for instance), no problem.
But what if I also have an industry vertical, and I need to be in both East, and the Manufacturing vertical?
This is the intended purpose of territories. In territories, I can be given record access based on two or more factors. I can be in one territory that identifies my geographical location, and the industry vertical and Account size (and as many other factors, potentially as I need).
But I've never implemented it. In fact few have implemented the new Territory Management features as it is a recent addition and replaces the old ugly Territory Management feature. So don't take my word for it, download the guide.
As to why your custom objects don't seem to be playing ball, that is explained in the guide where it states:
Territory management only affects accounts and the standard objects that have a master-detail relationship to accounts.
For example, opportunities are included in territory management but leads are not.
So for record-level permissions (also sometimes referred to as the Sharing Model, record access, record visibility) for custom objects, you must use roles and the role hierarchy.