There appear to be several issues here, the first its that the gtkcalendar
calculation for converting to its ordering of the days is wrong.  Second is that
the following test program:

#include <langinfo.h>
#include <stdio.h>

int
main (int argc, char **argv)
{
        char *week_start;

        week_start = nl_langinfo (_NL_TIME_FIRST_WEEKDAY);
        printf ("Week start day %d\n", *week_start);
        printf ("Gtk calculated week start day %d\n", *((unsigned char *)
week_start) % 7 - 1);

}

Yields the following results:
jpr@bishop:~> ./langinfo
Week start day 7
Gtk calculated week start day -1
jpr@bishop:~> LC_ALL=cs_CZ.UTF-8 ./langinfo
Week start day 7
Gtk calculated week start day -1

Meaning that cs_CZ.UTF-8 and the default locale (for me LANG=en_US.UTF-8) both
have the same day for the week start.

Then the output of locale is:
jpr@bishop:~> locale -k -c LC_TIME
LC_TIME
abday="Sun;Mon;Tue;Wed;Thu;Fri;Sat"
day="Sunday;Monday;Tuesday;Wednesday;Thursday;Friday;Saturday"
abmon="Jan;Feb;Mar;Apr;May;Jun;Jul;Aug;Sep;Oct;Nov;Dec"
mon="January;February;March;April;May;June;July;August;September;October;November;December"
am_pm="AM;PM"
d_t_fmt="%a %d %b %Y %r %Z"
d_fmt="%m/%d/%Y"
t_fmt="%r"
t_fmt_ampm="%I:%M:%S %p"
era=
era_year=""
era_d_fmt=""
alt_digits=
era_d_t_fmt=""
era_t_fmt=""
time-era-num-entries=0
time-era-entries="S"
week-ndays=7
week-1stday=19971201
week-1stweek=4
first_weekday=1
first_workday=1
cal_direction=1
timezone=""
date_fmt="%a %b %e %H:%M:%S %Z %Y"
time-codeset="UTF-8"

and:

jpr@bishop:~> LC_ALL=cs_CZ.UTF-8 locale -c -k LC_TIME
LC_TIME
abday="Ne;Po;Út;St;Čt;Pá;So"
day="Neděle;Pondělí;Úterý;Středa;Čtvrtek;Pátek;Sobota"
abmon="led;úno;bře;dub;kvě;čen;čec;srp;zář;říj;lis;pro"
mon="leden;únor;březen;duben;květen;červen;červenec;srpen;září;říjen;listopad;prosinec"
am_pm=";"
d_t_fmt="%a %e. %B %Y, %H:%M:%S %Z"
d_fmt="%d.%m.%Y"
t_fmt="%H:%M:%S"
t_fmt_ampm="%I:%M:%S"
era=
era_year=""
era_d_fmt=""
alt_digits=
era_d_t_fmt=""
era_t_fmt=""
time-era-num-entries=0
time-era-entries="N"
week-ndays=7
week-1stday=19971130
week-1stweek=0
first_weekday=1
first_workday=1
cal_direction=1
timezone=""
date_fmt="%a %b %e %H:%M:%S %Z %Y"
time-codeset="UTF-8"

So that nl_langinfo is returning '7' while the first_weekday value of locale is
'1'.  

I've googled for the number->day mapping but I see both 1 (sunday) to 7
(saturday) and 1 (monday) to 7 (sunday) for locale output.

CC'ing kukuk for some insight.

Ping

You didn't call setlocale. 

Even when setting  LC_ALL=cs_CZ.UTF-8? 

??? 

As in why do i need to call setlocale if I set the LC_ALL environment variable.
 Especially when i'm using the "locale" command line tool.

Ignore #6.

Ok, from http://lists.debian.org/debian-i18n/2005/07/msg00039.html I found the
following snippet which appears to indicate that nl_langinfo changed from 1
(Sunday) to 7 (Saturday) to 1 (Monday) to 7 (Sunday):

> Programers use nl_langinfo() to access to locale information, but they
> have no standard way to determine if nl_langinfo(DAY_1) refers to Sunday
> or Monday.  Moreover all existing cal-like programs get instantly broken
> if nl_langinfo(DAY_1) becomes Monday instead of Sunday, which is why I
> am stating that ISO 14652 is breaking compatibility, not adding
> features.
> It would IMHO have been much better to define new keywords when
> POSIX definitions are altered in such an incompatible way.

The change with Monday first was because we got a number of comments
saying that it was not logical to specify Sunday first, for a number of
cultures. So we figured that people want to specify their first 
weekday, first...

I also don't believe this rises to the level of major, but it should be reviewed
for this and any other apps that call it.

Created attachment 49092 [details]
gtk+-first_weekday.patch

Proposed patch for gtk+-2.8.3.

Works for me for latest glibc and C en_US.UTF-8 and cs_CZ.UTF-8 locales.

I guess that it maybe will not work properly in 9.3, so I will submit it as %if
%suse_version > 930.

Patch submitted for RC2.

Reopening. With upstream fix from gtk+-2.8.6 it does not work again, at least for cs_CZ.UTF-8. http://bugzilla.gnome.org/show_bug.cgi?id=314473

I am not sure, whether bug is in gtk, glibc or in localedata.

Note: Tested in supplementary. Needs recheck in 10.1.

It looks like the locale data:

week-1stday=19971130 (Sunday)
first_weekday=1 (Sunday because of week-1stday)

cs_CZ has no week information, so it defaults to C.  Someone should check the official definition.

Reassingning to glibc maintainer to ensure, that all locales of 10.1 will contain correct week information.

That needs to be fixed by this people who are responsible for this definitions and have the knowledge, means upstream responsible. I can nothing do here.

*** Bug 145331 has been marked as a duplicate of this bug. ***

I think we should at least fix the US locale, all the complaints so far have originated from there.

I can check Czech and some European languages.

Created attachment 69816 [details]
glibc-2.3.90-locale-weekstart.diff

Patch to add week keyword to some locales

Thorsten, can you include (and forward to upstream) the above patch then?
It was generated from Gtk+ calendar po files. 

I will only include this, if it is upstream.
Please send it upstream (for example glibc bugzilla), since you know more about it , I know nothing and cannot argument.

http://sources.redhat.com/bugzilla/show_bug.cgi?id=2388

It's reported upstream and hopefully appears in the CVS some day. I can't do
more about that, so I'll reassign back to you.

Later if upstream decission was taken.

Upstream bug was marked as fixed. Reopening to remove temporary work-arounds.

Reassigning to me.

And setting to NEEDINFO:

Please let me know after checking these locale fixes into OpenSUSE.

We plan to take glibc-2.7 once gcc settles a bit again.

Go ahead Petr, gcc is in STABLE :)

New glibc is in.

Disabling the _NL_TIME_FIRST_WEEKDAY hack for OpenSUSE > 1030 and moving back from gtk2 specific week info checking to glibc locales.

If there will be more problems again, it will be reverted.

If there will be minor problems only, glibc locales will be fixed.