Нужно класть фоны в блоки, охватывающие обе колонки одновременно.

Нужно перед закрывающим тэгом (например, </div>) охватывающего блока поставить дополнительный элемент с высотой 0 и clear: both;