Count showing as 0 in View, while it shows as correct on node view

Same problem here, clearing the cache sets the counts to new/correct values... But that should be done without clearing the cache every time something is inserted... right?

No, I'm afraid that's just how caching works. Whether it is data from node reference count or some other field, if your cache expires once an hour then whatever your cached values are will be displayed for that hour, even if you change those values, unless the cache is rebuilt manually. I am assuming you are using time based cache invalidation. You may want to check out http://drupal.org/project/views_content_cache. I haven't used it, but it is supposed to invalidate the cache whenever content changes, which sounds like what you are after. That will only help with the Views cache though. If you have other layers of caching, the page cache for anonymous users, block cache, or a reverse proxy like Varnish, for instance, then you will need to adjust your caching strategies to account for that. Increasing the frequency of cache rebuilds may also be appropriate (every 5 minutes instead of every hour, maybe), depending on your needs.