Well they do two different things.
Tasker allows you to react to absolutely anything (or combination of anything) that the phone can detect, receive, calculate, process, or whatever it can get from any of its inputs or sensors, and then react to them by doing absolutely anything the phone is capable of doing (submitting a form via HTTP POST, encrypting something, turning WiFi or GPS off/on, displaying a custom notification, sending a text, etc). For example, I have it put the phone on silent if it's plugged into the mains charger (not a PC) and is face down after midnight but before 9am (i.e. when I'm asleep), and automatically come out of silent when those conditions are no longer true. I have it send me a URL shortened link to its location on Google Maps and the MAC addresses of all WiFis in range via SMS if I send it a secret password by text in case its lost or stolen. I also have it turn auto-rotate on for specific apps, GPS on when specific apps start, etc. It can do everything Locale can do and 1,000x more. It's very well written, and doesn't send personal information to 3rd party companies without your permission (shame on you Locale).
AutoStarts looks at what receivers each app has for the multitude of Android intents that exist (there's like a hundred), for example when an SMS is received, when an app is installed, when bootup has completed, when the camera button is pressed, when the time has been changed, etc, and block them on an individual basis. If you've ever used a Task Killer and killed off an app only to see it has started itself 10 minutes later you'll know what I mean. So, as a random example, when an SMS is received, the Messaging app will react to this, but on my phone Handcent, Yahoo, and Software Update also react to this. I don't want Yahoo starting every time I get an SMS, so I block Yahoo from receiving that intent. Similarly, when the Camera Button is pressed, the Camera app runs (obviously), but so does Handcent (it has an option to send picture messages) and Facebook (so you can upload it to your profile). I don't want either of those lagging my phone by simultaneously starting with the Camera app when I'm trying to take a picture quickly. Of course, one of the biggest intents it can tweek is BOOT_COMPLETED, which is what starts the majority of apps on startup.
So, Tasker is used to do cool amazingly powerful things with your phone based on the phones contextual situation. AutoStarts can be used to stop tons of apps running randomly for hundreds of stupid reasons.