Headrests are something u get used to but if u're really having trouble, try getting the Honda service guys to try and get you the fabric one... not sure if it'll work out well (or even look remotely decent) but it might work. :S

I say give it time. Don't rush because the leather ones will be nicer (and better for resale) in the long run (assuming they're in gd condition).