This might sound like a stupid question, but do the directories you are uploading to actually exist? If you are trying to upload to a child directory that doesn't exist, you'd have to use mkdir first.
I've worked a lot with CI and ajax uploaders, and not had any problems related to sessions. I think blaming sessions is common, but you could remove the need for a session, and then does you uploader then start working? Probably not.
Does the ajax uploader you are working with provide any debugging info sent to console? What uploader is it? Just for kicks, you could try out the uploader that is demonstrated in Community Auth. It definitely works, and I'm using it on a production website where thousands of files have been uploaded using it. No session problems. Windows, Linux, Mac ... no problems. Windows server, Linux server ... no problems.
