I don't have Python code for this (I have Java), but the problem you're stumbling with is pretty much independent from the language you use, and it is always good to be able to see some code where you need to have all the details. You just need to do the requests I do, and verify some of the details I highlight and check if it might be your problem.
You can use this to remove the star for a given post (note that this service supports more than one item at the same time if you need that):
String authToken = getGoogleAuthKey();
// I use Jsoup for the requests, but you can use anything you
// like - for jsoup you usually just need to include a jar
// into your java project
Document doc = Jsoup.connect("http://www.google.com/reader/api/0/edit-tag")
// this is important for permission - more details on how to get this ahead in the text
.header("Authorization", _AUTHPARAMS + authToken)
.data(
// you don't need the userid, the '-' will suffice
// "r" means remove. you can also use "a" to add
// you have lots of other options besides starred. e.g: read
"r", "user/-/state/com.google/starred",
"async", "true",
// the feed, but don't forget the beginning: feed/
"s", "feed/http://www.gizmodo.com/index.xml",
// there are 2 id formats, easy to convert - more info ahead in the text
"i", "tag:google.com,2005:reader/item/1a68fb395bcb6947",
// another token - this one for allow editing - more details on how to get this ahead in the text
"T", "//wF1kyvFPIe6JiyITNnMWdA"
)
// I also send my API key, but I don't think this is mandatory
.userAgent("[YOUR_APP_ID_GOES_HERE].apps.googleusercontent.com")
.timeout(10000)
// VERY IMPORTANT - don't forget the post! (using get() will not work)
.post();
You can check my answer in this other question for some more implementation details (the ones referred to on the comments).
To list all the starred items inside a feed, you can use http://www.google.com/reader/api/0/stream/items/ids or http://www.google.com/reader/atom/user/-/state/com.google/starred . You can use these ids to call the above mentioned API for removing the star.
These last 2 are a lot easier to use. You can check details on the API on these unoffical (but nicely structured) resources: http://www.chrisdadswell.co.uk/android-coding-example-authenticating-clientlogin-google-reader-api/ , http://code.google.com/p/pyrfeed/wiki/GoogleReaderAPI , http://blog.martindoms.com/2009/10/16/using-the-google-reader-api-part-2
Hope it helps!