I think you are right. You must check-in with the carrier operating the first leg of your travel day. This from FAQ concerning check-in at nwa.com:

"Can I use nwa.com check-in if my itinerary includes travel on other carriers?
Your E-Ticket or reservation may contain flight segments on other airlines. Self-service check-in is available for the following flights:

All regularly scheduled flights operated by Northwest Airlines (including Airlink partners, Mesaba and Pinnacle Airlines)*
KLM-operated flights originating in the U.S.
Connecting flights operated by KLM Royal Dutch Airlines, Continental Airlines, Delta Air Lines, Alaska Airlines, Horizon Air and Hawaiian Airlines. The first originating flight must be operated by Northwest Airlines(except KLM flights where indicated).
*nwa.com check-in is available for Northwest operated flights from London's Gatwick Airport. Check-in on klm.com for all other Northwest/KLM operated flights from Europe. Online check-in is not yet available for flights from Paris, France."


In this case, as the first flight is on KLM and not originationg in the US, check-in must be done at klm.com. However, you can check-in 30 hrs prior to your flight with KLM. All you need is your e-ticket number.

I did this a while back going from ARN-AMS-MSP-SEA. It worked quite well, as I was able to change my seat on the KLM leg to AMS.

I do remember some sort of a glitch....something to the effect of checking in for the first leg checks you in for all other legs, thus I was not able to check in for the first leg on KLM (which left at 10am) until I was within 24 hrs of departure on the AMS-MSP leg on NW (which left at 2pm), as NW has a more restrictive 24 hr check-in limitation. TSA or something.

Hope you are able to get the seats you desire.