Paging not working in 1.5

Hi, just upgraded to 1.5. Everything seems to be working fine except my paging (previous/next within category) I get a 404. I am using rewrite. Look at:

http://www.pixelmech.com/notebook/category/animation/

Click on previous entries – you get this URL

http://www.pixelmech.com/notebook/category/animation/page/2/

Which is a 404. I upgraded another site to 1.5 and am using probably near identical rewrite and it works fine. Maybe this is a template problem or something?

My permalink structure is:
/notebook/%year%/%monthnum%/%postname%

Here are my rewrite rules:
——————————————–
Options FollowSymlinks
RewriteEngine On
RewriteBase /
RewriteRule ^notebook/category/(.*)/(feed|rdf|rss|rss2|atom)/?$ /wp-feed.php?category_name=$1&feed=$2 [QSA]
RewriteRule ^notebook/category/?(.*) /index.php?category_name=$1 [QSA]
RewriteRule ^notebook/author/(.*)/(feed|rdf|rss|rss2|atom)/?$ /wp-feed.php?author_name=$1&feed=$2 [QSA]
RewriteRule ^notebook/author/?(.*) /index.php?author_name=$1 [QSA]
RewriteRule ^notebook/([0-9]{4})?/?([0-9]{1,2})?/?([_0-9a-z-]+)?([0-9]+)?/?$ /index.php?year=$1&monthnum=$2&name=$3&page=$4 [QSA]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([_0-9a-z-]+)?/(feed|rdf|rss|rss2|atom)/?$ /wp-feed.php?year=$1&monthnum=$2&name=$3&feed=$4 [QSA]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([_0-9a-z-]+)?/trackback/?$ /wp-trackback.php?year=$1&monthnum=$2&name=$3 [QSA]
RewriteRule ^feed/?([_0-9a-z-]+)?/?$ /wp-feed.php?feed=$1 [QSA]
RewriteRule ^comments/feed/?([_0-9a-z-]+)?/?$ /wp-feed.php?feed=$1&withcomments=1 [QSA]
RedirectPermanent /index.xml http://www.pixelmech.com/feed/rss2/
RedirectPermanent http://www.pixelmech.com/index.php?id=P74 http://www.pixelmech.com/notebook/2004/05/3d-box-model-in-black-and-white
RedirectPermanent http://www.pixelmech.com/index.php?id=P54 http://www.pixelmech.com/notebook/2003/12/troubled-borders
RedirectPermanent http://www.pixelmech.com/index.php http://www.pixelmech.com/
ErrorDocument 404 /404.php

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} -f [OR]
RewriteCond %{REQUEST_FILENAME} -d
RewriteRule ^.*$ – [S=35]
RewriteRule ^feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?&feed=$1 [QSA,L]
RewriteRule ^(feed|rdf|rss|rss2|atom)/?$ /index.php?&feed=$1 [QSA,L]
RewriteRule ^page/?([0-9]{1,})/?$ /index.php?&paged=$1 [QSA,L]
RewriteRule ^comments/feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?&feed=$1&withcomments=1 [QSA,L]
RewriteRule ^comments/(feed|rdf|rss|rss2|atom)/?$ /index.php?&feed=$1&withcomments=1 [QSA,L]
RewriteRule ^comments/page/?([0-9]{1,})/?$ /index.php?&paged=$1 [QSA,L]
RewriteRule ^search/(.+)/feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?s=$1&feed=$2 [QSA,L]
RewriteRule ^search/(.+)/(feed|rdf|rss|rss2|atom)/?$ /index.php?s=$1&feed=$2 [QSA,L]
RewriteRule ^search/(.+)/page/?([0-9]{1,})/?$ /index.php?s=$1&paged=$2 [QSA,L]
RewriteRule ^search/(.+)/?$ /index.php?s=$1 [QSA,L]
RewriteRule ^notebook/category/(.+)/feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?category_name=$1&feed=$2 [QSA,L]
RewriteRule ^notebook/category/(.+)/(feed|rdf|rss|rss2|atom)/?$ /index.php?category_name=$1&feed=$2 [QSA,L]
RewriteRule ^notebook/category/(.+)/page/?([0-9]{1,})/?$ /index.php?category_name=$1&paged=$2 [QSA,L]
RewriteRule ^notebook/category/(.+)/?$ /index.php?category_name=$1 [QSA,L]
RewriteRule ^notebook/author/([^/]+)/feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?author_name=$1&feed=$2 [QSA,L]
RewriteRule ^notebook/author/([^/]+)/(feed|rdf|rss|rss2|atom)/?$ /index.php?author_name=$1&feed=$2 [QSA,L]
RewriteRule ^notebook/author/([^/]+)/page/?([0-9]{1,})/?$ /index.php?author_name=$1&paged=$2 [QSA,L]
RewriteRule ^notebook/author/([^/]+)/?$ /index.php?author_name=$1 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})/feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?year=$1&monthnum=$2&day=$3&feed=$4 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})/(feed|rdf|rss|rss2|atom)/?$ /index.php?year=$1&monthnum=$2&day=$3&feed=$4 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})/page/?([0-9]{1,})/?$ /index.php?year=$1&monthnum=$2&day=$3&paged=$4 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([0-9]{1,2})/?$ /index.php?year=$1&monthnum=$2&day=$3 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?year=$1&monthnum=$2&feed=$3 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/(feed|rdf|rss|rss2|atom)/?$ /index.php?year=$1&monthnum=$2&feed=$3 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/page/?([0-9]{1,})/?$ /index.php?year=$1&monthnum=$2&paged=$3 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/?$ /index.php?year=$1&monthnum=$2 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?year=$1&feed=$2 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/(feed|rdf|rss|rss2|atom)/?$ /index.php?year=$1&feed=$2 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/page/?([0-9]{1,})/?$ /index.php?year=$1&paged=$2 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/?$ /index.php?year=$1 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([^/]+)/trackback/?$ /index.php?year=$1&monthnum=$2&name=$3&tb=1 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([^/]+)/feed/(feed|rdf|rss|rss2|atom)/?$ /index.php?year=$1&monthnum=$2&name=$3&feed=$4 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([^/]+)/(feed|rdf|rss|rss2|atom)/?$ /index.php?year=$1&monthnum=$2&name=$3&feed=$4 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([^/]+)/page/?([0-9]{1,})/?$ /index.php?year=$1&monthnum=$2&name=$3&paged=$4 [QSA,L]
RewriteRule ^notebook/([0-9]{4})/([0-9]{1,2})/([^/]+)/?([0-9]+)?/?$ /index.php?year=$1&monthnum=$2&name=$3&page=$4 [QSA,L]
</IfModule>

# END WordPress