Does your sim have either the "eye candy" or the "attractive" LTR or the "beauty" wish from the genie?
Any one or better still, combination of these, will give your sim a little boost which should solve your problem. Certain traits also help with this. The obvious one is charisma, but, "good sense of humour" should get your sim from friend to best friend in a single interaction. I find that sims with beauty, eye candy and attractive will sometimes become best friends with other sims simply by being in the same room, or having tthem pass by in the street if they have achieved the everybody's best friend challenge. Unfortunately, sims they were aquainted with before getting the best friend status are not affected and you still have to either work to bring them up in the usual way, or simply just forget about them.