In the second implementation, your API does seem a bit complex. Why not:
$cache->insert( tag => $key_obj, data => $obj );
@values = $cache->retrieve( tag => $key_obj )
or even
$cache->insert( $key_obj, $obj );
@values = $cache->retrieve( $key_obj )
and let the cache object deal with constructing your tags from $key_obj? Then the chances of making a mistake when constructing the tag are limited to your cache code internals, rather than all the callers. You'll also be able to change your tag structure in one place should it become necessary.
Also, just curious here, but what did you find lacking in the Cache::* modules?
