La concordance des temps nous fait préférer la première proposition :
Quand nous avons offert le cadeau l'an dernier, nous avons remarqué que certaines personnes étaient tristes.
passé composé + passé composé = les deux actions sont contemporaines.
-------------------------
Le plus-que-parfait conviendrait pour une action passée antérieure à une autre action passée :
Nous avions remarqué que certaines personnes étaient tristes. Alors, nous leur avons offert des cadeaux.
1. Observation de l'état de tristesse
2. Les cadeaux