I don't know if such an alliance would be feasible -- Austria was just as much opposed to Russian influence increasing in the Balkans as the Western Powers were, not to mention Schwarzenberg had no wish to aid Russia, despite Tsar Nicholas' betting that Austria might join them.
Assuming that is overridden though -- perhaps a different Prime Minister in Austria (earlier death of Schwarzenberg?) who supports an Austro-Russian alliance as a way of keeping the Habsburg Empire 'pacified.' Nevertheless, I don't think Austria would add any advantages to Russia, they might weigh them down, although they may be able to make some headway into Bosnia.
The fact of the matter is, Austria was in a terrible position after 1848: Hungary was under military rule, and she was also spending significant resources in Italy, where they hosted occupation forces in Modena and Tuscany, where the Duke and Grand Duke respectively were scions of the Habsburg dynasty, as well in Parma. In whole, Austria had played a huge part in ending the revolutionary in fervor and the entire peninsula was almost under Austrian bayonet, where the Austrian forces had even played a part with the French in ending the Roman Republic. Her finances were in disarray and she had a huge deficit throughout the 1850s. Her army certainly learned some lessons during 1848, but she probably doesn't have many resources available to sustain a large term offensive campaign without withdrawing forces from Hungary (which is still simmering and would be in a difficult situation until the Ausgeleich) or Italy.
Allied forces probably still win, I honestly can't see Austria tipping the balance for Russia. You probably get a similar Treaty of Paris. The Austrians probably aren't punished perse, but are probably forced to vacate their occupation of any Turkish territory. This probably includes Bosnia as well as Serbia: Austria probably certainly occupies the Serbian Principality much as Russia occupied the Danubian Principalities.
Sardinia Piedmont may or may not join the war if Austrian joins: they are still smarting from 1848, and whilst their joining of the Crimean War helped gain public support for Italian Unification, it probably isn't a wise idea. One interesting knock off effect if they do join, is that they probably end up getting another bloody nose from Austria. This could turn Italian unification away from Sardinia and perhaps give the Republican wing more popularity. Thus we see the Risorgimento take on a more Republican character and Italy ultimately unified in the 19th century as a Republic, rather than under the House of Savoy. Of course, France may divert forces from Russia to fight in Italy... which is certainly a case. But without any preparations (much like the war in 1859 was), Sardinia may be knocked out before France can send any considerable forces into Piedmont. If they do, we could see the Treaty of Paris grant Lombardy to Sardinia... but I am more willing to think Sardinia would be defeated or would sit out all together rather than that happening.
Austria, on the losing side of the Crimean War, most certainly sees great political unrest, and we probably see a move towards constitutional reform a few years earlier. Franz Josef's Prime Minister (assuming our POD is having someone else rather than Schwarzenberg take over in 1848/1849) is almost certainly forced to resign, and we probably see an earlier October Diploma which empowered the Reichsrat to some extent and essentially amounted to aristocratic federalism. If the Austrians are severely punished (say, Lombardy is lost and Italy under the Savoyards essentially unites a few years earlier), we may see the document be a bit more liberal, like the February Patent that was introduced in 1861.