Pagination resolving to first page only in WordPress

Building off of what Rarst has said, I'm pretty sure the query string will retain 'paged' queries even if WP_Query strips it out as irrelevant. You could try replacing your query posts line with this:

global $query_string;
parse_str( $query_string, $my_query_array );
$paged = ( isset( $my_query_array['paged'] ) && !empty( $my_query_array['paged'] ) ) ? $my_query_array['paged'] : 1;
query_posts('post_type=post&posts_per_page=3&paged='.$paged);