Since I have already been through the ringer on this one with the official Steam support (and also 2k tech support), I will paste my convos for context:

2k ticket:

STEAM CLOUD SYNCING DOES NOT WORK ON BIOSHOCK INIFINITE FOR LINUX
Avatar
Skerfy July 03, 2015 15:37
I just tested this, it does not work, according to the forums it does work for other platforms.

Avatar
Federico B. July 04, 2015 14:27
Hello Skerfy,

Thanks for contacting 2K Support!

I am sorry to hear that. Unfortunately this is more of a Steam Issue than a game issue. So I would strongly advise to contact Steam given I wouldn't be able to manipulate Steam Cloud in any way. To contact Steam Support please click here: https://support.steampowered.com/
Please let me know if you need further assistance, have a great day.

Federico B.
2K Support

Avatar
Skerfy July 06, 2015 15:09
I have not heard back from Steam regarding this issue. 
-- 
--- 
<ryanpcmcquen.org> Monday, 06 July 2015, 03:01PM -07:00 from [email protected] :

Avatar
Federico B. July 06, 2015 15:16
Hello there,

I understand this can be extremely frustrating. Unfortunately there is nothing we can do, since the service issue you are experiencing is related to a steam product. I wish I could contact Steam, but sadly that is not possible nor authorized. Having said that, I hope they answer you soon, don't loose hope. Should you have any further issue, please feel free to contact us.

Federico B.
2K Support

Avatar
Skerfy July 12, 2015 16:05
Steam has not replied to my support request yet. I already beat the game though ... 
-- 
--- 
<ryanpcmcquen.org> Sunday, 12 July 2015, 04:02PM -07:00 from [email protected] :

Avatar
Skerfy July 13, 2015 09:48
Ok, thanks for the help. You may close this ticket. 
-- 
--- 
<ryanpcmcquen.org> Sunday, 12 July 2015, 04:02PM -07:00 from [email protected] :

Avatar
Federico B. July 17, 2015 18:54
Hello there,

Sounds good, thanks again for contacting us. Have a wonderful day.

Federico B.
2K Support

Steam ticket:

Steam Cloud syncing does not work for this game
Ticket number   2551-WYCV-1290
Category    Game/DLC Questions > Installation Issues
Email   [email protected]
Product BioShock Infinite
Steam Account Login Name    psn_dotspc
Operating System    Linux
Modify Question Properties Print Question Close Ticket
This Question's Message(s) 
1 Message by you on Sat, Jul 4 2015 17:42
But it works for every other game. I contacted 2k support and they said that Steam was responsible for this.
2 Message by you on Sat, Jul 4 2015 17:43
The game is Bioshock Infinite.
3 Message by you on Wed, Jul 8 2015 17:39
This is not helpful: Please restart your computer and then follow the steps in our Troubleshooting Network Connectivity FAQ: https://support.steampowered.com/kb_article.php?ref=1456-EUDN-2493
4 Message by Support Tech Jimmy on Tue, Jul 14 2015 7:10
Hello,

Thank you for contacting Steam Support,

You are receiving this message in response to the “Steam Client > Network/Connection Issue” ticket that you submitted. 

We're sorry for the delay. We're currently experiencing much higher traffic than normal, and are asking anyone needing help to read the information below.

If you still need assistance, you *must* respond to this message after reviewing this information. Doing so will place you in queue for an expedited response. The information below is known to fix the majority of issues, and often times saves users a ticket. 

If you no longer require assistance, you can ignore this message and your ticket will close automatically.

Please start by following the steps in the guide below now, even if you've tried them previously on your own. 

Title: Troubleshooting Network Connectivity
Link: http://support.steampowered.com/kb_article.php?ref=1456-EUDN-2493

If this does not resolve your connection issue, please attach a diagnostic report for your system. We'll review this report for potential conflicts or issues, and provide you with an expedited response: 

For a PC:
Title: How to run and submit MSINFO32 Info reports
URL: http://support.steampowered.com/kb_article.php?ref=1376-WTZN-9132

For a Mac:
Title: System Profiler Reports 
Link: https://support.steampowered.com/kb_article.php?ref=4840-QWJX-0408

Thank you for your patience.
5 Message by you on Tue, Jul 14 2015 8:30
There is not actually a network issue, I just did not know which topic to choose, Steam Cloud works for every game but Bioshock Infinite.
--

---
<ryanpcmcquen.org> Tuesday, 14 July 2015, 08:11AM -07:00 from Steam Support < [email protected]> :
6 Message by Support Tech Jimmy on Wed, Jul 15 2015 10:35
Hello Ryan,

The Steam Cloud conflict window will come up when Steam isn't sure which files are the most recent or you have played the game from multiple computers since your last Steam Cloud sync. Please proceed with caution and backup your saved files on your current computer - if the save that you wish to keep is mistakenly overwritten, it is unlikely that you will be able to restore it unless you manually back it up ahead of time.

Please consider your most recent activity with this game carefully.

If you have a habit of forcing Steam to close before it can sync your saved games (this can happen if you shut down Windows quickly after quitting a cloud enabled game), make sure that you backup your local saves for the safest results.

If you last played the game on this computer, and you are sure that your current computer contains the most recent saves, you will want to upload from your current computer to the cloud.

If you last played this game on another computer, and you are sure that the other computer contains the most recent saves, you will want to download the saved files from the Steam Cloud.

If a friend played this cloud enabled game on your computer using their Steam account, you likely want to download your files from the cloud, as your friend's game may have overwritten your local saved data with their own.

If you have any further questions, please let us know - we will be happy to assist you.
7 Message by you on Wed, Jul 15 2015 10:47
Thank you for your reply, but you do not seem to understand the situation.


>
> The Steam Cloud conflict window will come up when Steam isn't sure which
> files are the most recent or you have played the game from multiple
> computers since your last Steam Cloud sync. Please proceed with caution and
> backup your saved files on your current computer - if the save that you wish
> to keep is mistakenly overwritten, it is unlikely that you will be able to
> restore it unless you manually back it up ahead of time.

Steam Cloud doesn't work in this game for Linux, for ANYONE, check the
Steam forums. I am not having a sync conflict, so I am unsure why you
brought this up.


> If you have a habit of forcing Steam to close before it can sync your saved
> games (this can happen if you shut down Windows quickly after quitting a
> cloud enabled game), make sure that you backup your local saves for the
> safest results.
>

I am pretty sure I already stated this, but I am on Linux. And I am
not force closing Steam before the sync finishes, the sync appears to
be happening, but it isn't actually saving the files. Are you able to
successfully use Steam Cloud with Bioshock Infinite on SteamOS or
Linux on your end?
8 Message by Support Tech Jimmy on Thu, Jul 16 2015 10:03
Hello Ryan,

When you say it does not work, can you be more specific? Please provide a description of what you are doing, what you're expecting to see, and what you're seeing instead.

Please also provide a link to the forum thread(s) to which you are referring.

Finally please provide a screenshot of any relevant errors or unusual behavior you are seeing.

Follow the link below for information:

Title: Saving a Screenshot on Linux
Link: http://support.steampowered.com/kb_article.php?ref=2767-WKLC-0354
9 Message by you on Sun, Jul 19 2015 7:25
OK, here are some forum posts where people cite issues with Steam Cloud in Bioshock Infinite (the issue only seems to occur on Mac OS and Linux):

https://steamcommunity.com/app/8870/discussions/0/618458030663652155/
https://steamcommunity.com/app/8870/discussions/0/864979455443845760/
https://steamcommunity.com/app/8870/discussions/0/530645446325087406/
https://steamcommunity.com/app/8870/discussions/0/864971765754658512/
https://steamcommunity.com/app/8870/discussions/0/828934724045081640/
http://forums.macrumors.com/threads/anyone-playing-bioshock-infinite-on-mac-steam-version.1763903/
https://steamcommunity.com/app/8870/discussions/0/616187839246221054/

When I say it does not work, I mean that my save files are completely gone on a new install, see this screenshot:

https://clbin.com/j1HPRh.png
10 Message by Support Tech Jimmy on Thu, Jul 23 2015 12:27
Hello Ryan,

Your saved games are in you Steam cloud (I'm able to see them), so it's unclear why they would not be synchronizing. Are you using a different OS on the two computers you're using? Please note that saved games are not always compatible between two different operating systems.
11 Message by you on Thu, Jul 23 2015 12:42
I have only ever played the game on Linux (Slackware Linux).
12 Message by Support Tech Jimmy on Thu, Jul 30 2015 14:59
Hello Ryan,

We apologize for the delay.

We are investigating this issue further. As soon as we have more information, we will update your ticket.
13 Message by you on Thu, Jul 30 2015 15:01
Thank you for the update.
14 Message by Support Tech Jimmy on Tue, Aug 11 2015 10:59
Hello Ryan,

We apologize for the delay.

Steam for Linux is currently only supported on Ubuntu 12.04/12.10 with Unity, Gnome, or KDE desktops.

If you are running another distribution of Linux, we will not be able to provide support. We recommend you install Ubuntu 12.04/12.10 for the best Steam experience on Linux.

For more information on this please visit the following link: https://wiki.ubuntu.com/Valve

If you wish to attempt to run Steam on a different distribution, it's best that you use Github to discuss them with our developers and other Linux users.

You can create a free Github account here:
https://github.com/signup/free

Once signed up and logged in you can visit our Github here and post your questions directly to the Linux Community and our developers:
https://github.com/ValveSoftware

If you have any further questions, please let us know - we will be happy to assist you.
15 Message by you on Tue, Aug 11 2015 17:18
Hi Jimmy,

This issue has nothing to do with my distribution. The path for the files is exactly the same on Ubuntu 12.04 as it is on Slackware:

~/.steam/steam/userdata/{USER_ID}/8870

All steam cloud does is copy some files to a certain directory, probably using some utility like rsync. But just to prove my point, I installed a fresh copy of Ubuntu 12.04 and installed Steam, then Bioshock Infinite. Guess what? The files are not there.

See screenshot(also attached):

https://clbin.com/KYYVDw.png

What is it going to take to convince you this is a genuine bug in the Steam client?
Screenshot from 2015-08-11 18:06:45.png - View Image (File Size : 311.7 KB)
16 Message by Support Tech Jimmy on Fri, Aug 14 2015 12:07
Hello Ryan,

If this issue is isolated to a single game, it's highly unlikely that we are dealing with a Steam bug. Developers/publisher are responsible for integrating their games with Steamworks and I would highly recommend continuing to troubleshoot with them.

However, if you wish to continue pursuing this as a Steam bug, it would be best that you use Github to discuss the issue with our developers directly.

You can create a free Github account here:
https://github.com/signup/free

Once signed up and logged in you can visit our Github here and post your questions directly to our developers as they can assist with these issues better and more efficiently:
https://github.com/ValveSoftware

If you have any further questions, please let us know - we will be happy to assist you.
17 Message by you on Fri, Aug 14 2015 20:41
Wow, this tech support is laughable. Thank you for wasting my time.

Needless to say I am pretty frustrated. This is clearly a bug.