おそらく、最初のクエリを次のように変更します:
db.userlinks.update (
{_id: 1, tags: {$nin: [{tag:'foo'}]}},
{$push: {'tags': {tag:'foo', links:[]}}},
{upsert: true}
)
$ push操作は、タグではなく、リンクにのみ影響する必要があります。
{$push: {'tags.links': {link: 'http://www.google.com', date: '123'} } },