Now something strange is happening:
Level 1:

Level 2:


01.level (the data for placing enemies, the endpoint and the player) is being loaded for level 2 as well.  Code is below.  (also notice all the extra things, for some reason they aren't being cleared...) they should have been since the screen is cleared when the level loads, and a new TileMapper object is used to handle the level data.
I'm pretty sure the problems lie within LoadLevel.py main.py or Screen.py

My game runs at a near steady 30fps on my Nexus 7, but struggles on my Galaxy Nexus.  The problem is the GNex is a fairly powerful phone and it is struggling with this.
I don't know what exactly is making it run so slowly.  I know that it shouldn't be as slow as it is.  I know, Python and Mobile device, but honestly I don't think it should be running as slowly as it is.

My code is as follows:

main.py
import pygame, math
try:
    import android
except ImportError:
    android = None
   
# Import our objects
from Player import Player
from Enemy import Enemy
from EndPortal import EndPortal
from Control import Controller
from LoadLevel import Level, TileMapper, LoadLevel
from Screen import GameScreen

clock = pygame.time.Clock()

def main():
    pygame.init()
    print "start game!"
   
    if android:
        android.init()
        android.map_key(android.KEYCODE_BACK, pygame.K_ESCAPE)
   
    mynative = pygame.display.list_modes()
    s_res = (mynative[0][0],mynative[0][1])
    screen = pygame.display.set_mode(s_res,pygame.FULLSCREEN)
    # Level Surface
    currentLevel = 0
    gameState = "levelLoad"
    scroll_x = 0
    scroll_y = 0
    if android:
        s = android.assets.open("bg.png")
    else:
        s = "../assets/bg.png"
    stars = pygame.image.load(s).convert()
   
    if android:
        # Setup Onscreen Controller
        controllerList = pygame.sprite.Group()
        middle = Controller(96,mynative[0][1]-192,"none")
        controllerList.add(middle)
        upArrow = Controller(96,mynative[0][1]-288,"up")
        controllerList.add(upArrow)
        downArrow = Controller(96,mynative[0][1]-96,"down")
        controllerList.add(downArrow)
        leftArrow = Controller(0,mynative[0][1]-192,"left")
        controllerList.add(leftArrow)
        rightArrow = Controller(192,mynative[0][1]-192,"right")
        controllerList.add(rightArrow)
        upleftArrow = Controller(0,mynative[0][1]-288,"upleft")
        controllerList.add(upleftArrow)
        uprightArrow = Controller(192,mynative[0][1]-288,"upright")
        controllerList.add(uprightArrow)
        downleftArrow = Controller(0,mynative[0][1]-96,"downleft")
        controllerList.add(downleftArrow)
        downrightArrow = Controller(192,mynative[0][1]-96,"downright")
        controllerList.add(downrightArrow)
           
    done = True
   
    if android:
        pygame.event.set_allowed([pygame.QUIT, pygame.KEYDOWN, pygame.MOUSEMOTION, pygame.MOUSEBUTTONUP])
    else:
        pygame.event.set_allowed([pygame.QUIT, pygame.KEYDOWN, pygame.KEYUP])
       
    tickClock = 0

    while done == True:
       
        if tickClock == 30:
            print math.floor(clock.get_fps())
            tickClock = 0
           
        tickClock += 1
       
        if gameState == "levelLoad":
            currentLevel += 1
            if (currentLevel.__str__().zfill(2)+".png") in android.assets.list():
                screen.fill((255,255,255))
                level = None
                newLevel = None
                tMap = None
                player = None
                endPortal = None
                level = pygame.Surface((640,416))
                level.fill((255,255,255))
                newLevel = LoadLevel(currentLevel.__str__().zfill(2)+".level")
                tMap = TileMapper(newLevel)
                level.blit(stars,(0,0))
                myLevel = Level(currentLevel.__str__().zfill(2)+".png")
                level.blit(myLevel.image,(0,0))
                player = tMap.player
                endPortal = tMap.endPortal
                gameLevel = GameScreen(level)
                dirties = []
                for e in tMap.enemyList:
                    dirties.append(e.rect)     
                gameLevel.drawScreen(screen,tMap,scroll_x,scroll_y)
                pygame.display.flip()
                gameState = "level"
            else:
                done = False
        # Track event happening
        for event in pygame.event.get():
            if event.type == pygame.KEYDOWN:
                if event.key == pygame.K_ESCAPE:
                    print "Quitting..."
                    done = False
            if android:
                # Movement
                if event.type == pygame.MOUSEMOTION:
                    mouse_pos = pygame.mouse.get_pos()
                    if upArrow.rect.collidepoint(mouse_pos):
                        player.change_x = 0
                        player.change_y = -3
                    elif downArrow.rect.collidepoint(mouse_pos):
                        player.change_x = 0
                        player.change_y = 3
                    elif leftArrow.rect.collidepoint(mouse_pos):
                        player.change_x = -3
                        player.change_y = 0
                    elif rightArrow.rect.collidepoint(mouse_pos):
                        player.change_x = 3
                        player.change_y = 0
                    elif upleftArrow.rect.collidepoint(mouse_pos):
                        player.change_x = -3
                        player.change_y = -3
                    elif uprightArrow.rect.collidepoint(mouse_pos):
                        player.change_x = 3
                        player.change_y = -3
                    elif downleftArrow.rect.collidepoint(mouse_pos):
                        player.change_x = -3
                        player.change_y = 3
                    elif downrightArrow.rect.collidepoint(mouse_pos):
                        player.change_x = 3
                        player.change_y = 3
                    else:
                        player.change_x = 0
                        player.change_y = 0
                elif event.type == pygame.MOUSEBUTTONUP:
                    player.change_x = 0
                    player.change_y = 0
            else:
                if event.type == pygame.KEYDOWN:
                    if event.key == pygame.K_LEFT:
                        player.changeSpeed(-3,0)
                    if event.key == pygame.K_RIGHT:
                        player.changeSpeed(3,0)
                    if event.key == pygame.K_UP:
                        player.changeSpeed(0,-3)
                    if event.key == pygame.K_DOWN:
                        player.changeSpeed(0,3)
                if event.type == pygame.KEYUP:
                    if event.key == pygame.K_LEFT:
                        player.changeSpeed(3,0)
                    if event.key == pygame.K_RIGHT:
                        player.changeSpeed(-3,0)
                    if event.key == pygame.K_UP:
                        player.changeSpeed(0,3)
                    if event.key == pygame.K_DOWN:
                        player.changeSpeed(0,-3)
        # Perform Updates
        if player.change_x or player.change_y:
            player.update(myLevel,tMap.enemyList)
            dirties.append(player.rect)
        for enemy in tMap.enemyList:
            enemy.update(myLevel)
        if endPortal.update(player):
            gameState = "levelLoad"
           
        # Check if Android version is not focused, if so pause the game           
        if android:   
            if android.check_pause():
                android.wait_for_resume()
               
        # Draw
        gameLevel.drawScreen(screen,tMap,scroll_x,scroll_y)
        if android:
            controllerList.draw(screen)
       
        # Game Camera
        # Buggy, always starts on top, but works.
        if (player.rect.y >= 208):
            if (gameLevel.scroll_y_limit >= 3) and player.change_y > 0:
                scroll_y += 3
        elif (player.rect.y <= 208):
            if (scroll_y > 0) and player.change_y < 0:
                scroll_y -= 3

        pygame.display.update(dirties)
        clock.tick(30)

# This isn't run on Android.
if __name__ == "__main__":
    main()


Player.py
'''
Created on May 20, 2013

@author: XVicarious
'''

import pygame

try:
    import android
except ImportError:
    android = None
   
class Player(pygame.sprite.DirtySprite):
   
    change_x = 0
    change_y = 0
   
    origin_x = 0
    origin_y = 0
   
    def __init__(self,x,y,scale = 1):
        pygame.sprite.DirtySprite.__init__(self)
        if android:
            sprite = android.assets.open("player.png")
        else:
            sprite = "../assets/player.png"
        self.image = pygame.image.load(sprite).convert_alpha()
        self.image = pygame.transform.scale(self.image,(self.image.get_width()*scale,self.image.get_height()*scale))
        self.rect = self.image.get_rect()
        self.rect.x = x
        self.origin_x = x
        self.rect.y = y
        self.origin_y = y
        self.mask = pygame.mask.from_surface(self.image)
    def changeSpeed(self,x,y):
        self.change_x += x
        self.change_y += y
    def update(self,wall,enemies):
        old_x = self.rect.x
        old_y = self.rect.y
        self.rect.x += self.change_x
        self.rect.y += self.change_y
        if pygame.sprite.collide_mask(self,wall):
                self.rect.x = old_x
                self.rect.y = old_y
        for anEnemy in enemies:
            if pygame.sprite.collide_mask(self,anEnemy):
                self.death()
     
    def death(self):
        self.rect.x = self.origin_x
        self.rect.y = self.origin_y

Wall.py (currently unused, using test level format)
'''
Created on May 21, 2013

@author: XVicarious
'''

import pygame

try:
    import android
except ImportError:
    android = None

class Wall(pygame.sprite.Sprite):

    def __init__(self,x,y,scale,t = 0):
        pygame.sprite.Sprite.__init__(self)
        if t == 0:
            if android:
                sprite = android.assets.open("wall.png")
            else:
                sprite = "../assets/wall.png"
        elif t == 1:
            if android:
                sprite = android.assets.open("ubridge.png")
            else:
                sprite = "../assets/ubridge.png"
        elif t == 2:
            if android:
                sprite = android.assets.open("ubridge2.png")
            else:
                sprite = "../assets/ubridge2.png"
        self.image = pygame.image.load(sprite).convert_alpha()
        self.image = pygame.transform.scale(self.image,(self.image.get_width()*scale,self.image.get_height()*scale))
        self.rect = self.image.get_rect()
        self.rect.x = x
        self.rect.y = y
        self.mask = pygame.mask.from_surface(self.image)

Enemy.py
import pygame
try:
    import android
except ImportError:
    android = None
   
class Enemy(pygame.sprite.DirtySprite):
   
    change_x = 0
    change_y = 0
    enemy_type = 0
   
    def __init__(self,x,y,etype,scale):
        pygame.sprite.DirtySprite.__init__(self)
        if etype == 0:
            if android:
                sprite = android.assets.open("enemy_horz.png")
            else:
                sprite = "../assets/enemy_horz.png"
        elif etype == 1:
            if android:
                sprite = android.assets.open("fastenemy_horz.png")
            else:
                sprite = "../assets/fastenemy_horz.png"
        elif etype == 2:
            if android:
                sprite = android.assets.open("enemy_vert.png")
            else:
                sprite = "../assets/enemy_vert.png"
        elif etype == 3:
            if android:
                sprite = android.assets.open("fastenemy_vert.png")
            else:
                sprite = "../assets/fastenemy_vert.png"
        self.image = pygame.image.load(sprite).convert_alpha()
        self.image = pygame.transform.scale(self.image,(self.image.get_width()*scale,self.image.get_height()*scale))
        self.rect = self.image.get_rect()
        self.rect.x = x + 3
        self.rect.y = y + 3
        self.mask = pygame.mask.from_surface(self.image)
        self.enemy_type = etype
        if self.enemy_type == 0:
            self.change_x = -6
        elif self.enemy_type == 1:
            self.change_x = -12
        elif self.enemy_type == 2:
            self.change_y = -6
        elif self.enemy_type == 3:
            self.change_y = -12
    def update(self,wall):
        self.rect.x += self.change_x
        self.rect.y += self.change_y
        if pygame.sprite.collide_mask(self, wall):
            self.change_x *= -1
            self.change_y *= -1
            self.rect.x += self.change_x
            self.rect.y += self.change_y
        self.dirty = 1

LoadLevel.py
'''
Created on May 23, 2013

@author: XVicarious
'''
import base64, pygame
from Wall import Wall
from Player import Player
from EndPortal import EndPortal
from Enemy import Enemy
try:
    import android
except ImportError:
    android = None
   
class LoadLevel(object):
   
    levelList = []
   
    def __init__(self, levelNumber):
        print levelNumber
        if android:
            level64 = android.assets.open(levelNumber)
        else:
            level = "../assets/" + levelNumber
            level64 = open(level,'r')
        levelString = base64.standard_b64decode(level64.read())
        for line in levelString:
            for char in line:
                if char == '\r' or char == '\n':
                    foo = "bar"
                else:
                    self.levelList.append(char)
       
class TileMapper(object):

    enemyList = pygame.sprite.Group()
    extraList = pygame.sprite.Group()
    player = None
    endPortal = None
   
    def __init__(self,levelList,scale = 1):
        for i in range(0,13):
            for j in range(0,20):
                # 2 -- player
                # 3 -- Vertical Enemy
                # 4 -- Horizontal Enemy
                # 5 -- Fast Vertical Enemy
                # 6 -- Fast Horizontal Enemy
                if levelList.levelList[(i*20)+j] == '2':
                    self.player = Player(j*32,i*32,scale)
                    self.extraList.add(self.player)
                    print "Player", j*32, i*32
                elif levelList.levelList[(i*20)+j] == '3':
                    self.enemyList.add(Enemy(j*32,i*32,2,scale))
                elif levelList.levelList[(i*20)+j] == '4':
                    self.enemyList.add(Enemy(j*32,i*32,0,scale))
                elif levelList.levelList[(i*20)+j] == '5':
                    self.enemyList.add(Enemy(j*32,i*32,3,scale))
                elif levelList.levelList[(i*20)+j] == '6':
                    self.enemyList.add(Enemy(j*32,i*32,1,scale))
                elif levelList.levelList[(i*20)+j] == '9':
                    self.endPortal = EndPortal(j*32,i*32)
                    self.extraList.add(self.endPortal)

class Level(pygame.sprite.Sprite):
   
    def __init__(self,image,levelData = None):
        pygame.sprite.Sprite.__init__(self)
        if android:
            sprite = android.assets.open(image)
        else:
            sprite = "../assets/" + image
        self.image = pygame.image.load(sprite).convert_alpha()
        self.rect = self.image.get_rect()
        self.mask = pygame.mask.from_surface(self.image)


Screen.py
'''
Created on Jun 3, 2013

@author: xvicarious
'''

import pygame

class GameScreen(object):
   
    mynative = None
    drawnScreen = None
    levelSurf = None
    newHeight = None
    scroll_y_limit = None

    def __init__(self, levelSurface):
        self.mynative = pygame.display.list_modes()
        self.newHeight = (416*self.mynative[0][0])/640
        self.levelSurf = levelSurface
        self.drawnScreen = levelSurface.copy()
       
    def drawScreen(self,screen,map,scroll_x,scroll_y):
        self.drawnScreen.blit(self.levelSurf,(0,0))
        map.enemyList.draw(self.drawnScreen)
        map.extraList.draw(self.drawnScreen)
        levelScaled = pygame.transform.scale(self.drawnScreen,(self.mynative[0][0],(416*self.mynative[0][0])/640))
        self.scroll_y_limit = self.newHeight - (self.mynative[0][1] + scroll_y)
        subSurfLevel = levelScaled.subsurface((scroll_x, scroll_y, self.mynative[0][0], self.mynative[0][1]))
        screen.blit(subSurfLevel,(0,0))
       

Note that this is my first project in Python with classes etc.

This really isn't an open source game.  I trust you guys, and I know it is a public topic but I doubt many will see it.

And thank you very much for the help.  As I've said in the project topic, Omnimaga members get a free copy.