Vietnamese Sandwiches - Spread Identification?
Pate can vary in color depending on what you put in it, so I'd say what you were eating was pate! 

Here's a pate recipe with a resultant gray hue: http://berriesandspice.com/vietnamese-banh-mi-pate/