Over the past year I've found that most issues people have getting this plugin boil down to four things. Here they are with bolded titles for easy scanning. :)
* The correct format for the request column is something like '/about.html' and is a relative path from the wordpress home page. The correct format for the destination column is a full url like 'http://yoursite.com/about/'. This is because you can only process requests that wordpress handles but you can redirect to any page on the web.
* The presence of a static file at the request URL. If you're redirecting /about.html and you have a file with that name left over from an old site, wordpress (and thus the plugin) won't process the request. You can fix this by deleting, moving, or renaming the file.
* Caching plugins like wp-super-cache can conflict with the plugin. This is because the authors give the plugin a very high priority, assuming no action should come before a cache check. This is mostly right, except in the case of page redirects. Anyway, the remedy to this is usually to disable and then re-enable the caching plugin. This should alter the order of plugin execution so that the 301 plugin will run first even though it has equal priority.
* Finally, if mod_rewrite is not enabled, the plugin won't work. I mention it last because it's very uncommon. If you have permalinks other than the default '/?p=xx' format, this is not the problem.