Nathan,
One last thing I thought of before looking at your account. Have you changed the name of the tabs? For example, changing the "Leads" tab to "My Leads"? If so, this could very well break the link that is setup in the actions for the button you're clicking on. Check to make sure that your tab is still labelled "Leads".
If you want to change your tab name, you can, however, you'll need to also update the actions in the "New Lead" button to point to the new location.
If that still doesn't fix it, I'll look into your account as see what it could be. Be careful when editing exisiting tabs and tab links as some screens look at the tab names in order to perform certain actions.
Hope that helps and have a good evening,
Danny