What operating system are you using? I've had several problems on Mac OSX that basically makes installing some extensions OVERLY painful. However, the Imagick install should be really simple, for most operating systems.
On your command line, type php -i | grep ini, and make sure the php.ini that is listed as being loaded is the same as the php.ini that phpinfo() says is being loaded. If these are different, that's where you have to start. Make sure extension=imagick.so is in both ini files, also - verify that they are loading extensions from the same directory (99% chance they will be, but who knows - you could be an exception).
After you've verified that (possibly) both php.ini files are loading imagick.so and it's still not working, try to tail -f /path/to/apache/error_log (assuming you're using apache, of course..) and restart apache. You're looking here for php warnings about loading libraries and/or extensions. Hopefully it will point you in the right direction.
Hope this helps,
Jim