In FoMT, talk to Van behind the counter (not over it). Then talk to him over the counter to look at his inventory, and he should sell the first record. Buy it, talk to Van one more time for good measure, and link up again. When you see him walking in Forget-Me-Not Valley, talk to him again, and then he should sell the same record on AWL too.
I think that's what I had to do - I remember being baffled as well that he wouldn't sell me a record.