Catch 404 after changing permalink structure from /%postname%/ to /%category%/%postname%/

That happens because WordPress reads your old post name as category name now – and it cannot find that category.

Solution: filter 404_template and try to find the post and its permalink. Then redirect.

<?php  # -*- coding: utf-8 -*-
/* Plugin Name: Redirect to category */

add_filter( '404_template', 't5_redirect_to_category' );

function t5_redirect_to_category( $template )
{
    if ( ! is_404() )
        return $template;

    global $wp_rewrite, $wp_query;

    if ( '/%category%/%postname%/' !== $wp_rewrite->permalink_structure )
        return $template;

    if ( ! $post = get_page_by_path( $wp_query->query['category_name'], OBJECT, 'post' ) )
        return $template;

    $permalink = get_permalink( $post->ID );

    wp_redirect( $permalink, 301 );
    exit;
}