Finding an injective mapping between two sets that maximizes a similarity function
The simplest counter-example is something like an "anti-multiplication table": for $A=B=\left\{1,2,\ldots,n\right\}$ let's define the cost function as $cost(a, b) = n^2 - ab$. The greedy algorithm will fail for $n \ge 2$.

The problem you are solving is called the assignment problem and it's well studied. It can be solved in polynomial time by the Hungarian algorithm, for example.