Turned out there are two fuses for the headlights, in addition to the relays. After swapping the relays and still having the problem, I checked all the fuses in the relay box in the engine bay. The one for my left headlight was blown. New fuse is in and it works like a charm. Thanks guys.