After trying just about everything (bananas (containing magnesium),
chamomile, ginkgo biloba, kava, kawakawa, L-theanine, lavender, lemon
balm, licorice root, marshmallow root, passionflower, St. John's wort,
tart cherry (containing melatonin), valerian, and warm milk (containing
tryptophan)) I've finally found a natural sleep aid that works for me:
Hops tea.

This is tea made from the same kind of hops (Humulus lupulus) as used
for brewing beer. It's fairly simple to make: Steep a small handful of
hops in a cup of boiled water for 7-10 minutes. Strain. Add a dash of
vodka (not necessary, but greatly improves the taste). Drink just before
bed.

If you're buying hops from a homebrew supplies shop, you want cone hops
(the whole thing, just dried) not the pellets. The exact variety isn't
important (I used Mosaic).