Page cache is just the cached values.
Cache tags are tags that are attached to a cached value (simplifying a little bit). This tells Drupal what cached values are related to what cache tags. When a cache tag is invalidated, all cached values that have the invalidated cache tag are invalidated as well. You can find more info on the Drupal documentation page about Cache Tags. The headline is:
Cache tags provide a declarative way to track which cache items depend on some data managed by Drupal.
So, answering your question, yes, they are totally related and you can (and you should) invalidate page cache entries using cache tags. Because, as stated above, cache tags track content and cache dependencies and thus you can invalidate cached item when content (or the source data of a cached item) changes.
However, this can be tricky. For example, page cache entry of a node view page is always associated with the cache tag node:[nid]. When the node is updated, that cache tag is invalidated, thus making the page cache of that node's view page invalidated as well. Views that shows a list of nodes are not associated with each node's cache tag. Blocks are other display elements may not be related to that kind of tags. So you need to know which cache tag you want to invalidate.
The good news is Drupal takes care of the most common cases, so you don't have to care. Usually, you only need to deal with the cache tags when you are developing custom code.
In your case, you may be hitting another cache (browser cache? reverse proxy cache?).