Hola, vilovo: Bienvenid@ a los foros. La frase correcta sería:"Qué café tan extraño paladean/ están paladeando mis labios". Suena como algo más bien poético. Sería más coloquial decir: "Qué gusto/sabor tan extraño tiene el café que estoy paladeando".
Ah!, si la pregunta era acerca del verbo "paladear", yo usaría "saborear": "Qué café tan extraño saborean mis labios".