This got ansible's fireball mode working for me from a clean Ubuntu 12.04 AWS instance. The tricky thing is that you will also need these dependencies deployed locally too - otherwise you'll get errors about zmq not being deployed. Currently, Ansible doesn't say if the missing dependency is on the server or client, which caused me much angst!

ansible_fireball_setup

---
- hosts: all
  sudo: yes
  user: ubuntu
  gather_facts: no
  connection: ssh
  tasks:
    - action: shell sudo aptitude update
    - apt: name={{ item }} state=installed
      with_items:
        - python-setuptools
        - python-dev
        - gcc
        - libzmq-dev
        - python-zmq
    - action: easy_install name=pip
    - action: pip name={{ item }} state=present
      with_items:
        - pyzmq
        - pyasn1
        - PyCrypto
        - python-keyczar # This needs to be on the server too!
    - action: fireball

- hosts: all
  connection: fireball
  tasks:
      - action: shell echo "Hello {{ item }}"
        with_items:
            - one
            - two